글 읽기 - [파이썬] 반례가 무엇일까요..?

mrkim882 2년 전 0

중간에 틀렸습니다 뜨는데

반례 찾아주시면 감사하겠습니다 ㅜㅜ

P = {}
for _ in range(sum(map(int, input().split()))):
    a, b = (map(int, input().split()))
    P[a] = b

queue = [(i,1) for i in range(2,8)]
check = [0] * 100
check[1] = 1
ans = 1010
while queue:
    n, cnt = queue.pop(0)
    
    if n > 100: continue
    if n==100: ans = min(ans,cnt); continue
    
    if check[n] == 0:
        check[n] = 1
        if n in P.keys():
            queue.append((P[n], cnt))
        queue.extend([(n+i,cnt+1) for i in range(1,7)])

print(ans)

kipa00 2년 전 2

반례입니다.

1
99
1

mrkim882 2년 전 0

정답 3으로 맞지 않나요??

kipa00 2년 전 0

뱀과 사다리가 존재하는 경우 무조건 올라타야 하는 것으로 알고 있습니다. 이 경우 정답은 4입니다.

clarification이 필요할지도 모르겠습니다.

mrkim882 2년 전 0

답변 감사합니다!

제가 이해를 잘 못한것같아서 하나만 더 질문드리겠습니다ㅜ

1. 1에서 6을 굴려 7로 이동

2. 7에서 5를 굴려 12로 이동, 사다리를 타고 99로 이동

3. 99에서 1을 굴려 100으로 이동

위 경로라면 3이 아닌가요??

뱀이나 사다리를 타는건 횟수에 포함이 안되는 것으로 이해하였습니다

kipa00 2년 전 3

앗... 시작이 1부터군요.

1
99
1

mrkim882 2년 전 0

감사합니다! 위에 케이스에서는 사다리나 뱀을 탄 것과 안 탄 경우가 모두 큐에 들어가는군요..

cmbyn 1년 전 3

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다.

7 1 이 인풋 케이스에 들어와도 되나요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 반례가 무엇일까요..?

mrkim882 2년 전 0

kipa00 2년 전 2

mrkim882 2년 전 0

kipa00 2년 전 0

mrkim882 2년 전 0

kipa00 2년 전 3

mrkim882 2년 전 0

cmbyn 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말