-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
마지막 인풋 테스트케이스 반례 질문입니다!
21.11.27 14:38 작성 조회수 179
0
안녕하세요! 질 좋은 강의에 감사인사부터 드립니다 :)
다름이 아니라 해당 문제에 대해 강사님의 아이디어만 듣고 스스로 구현해보았는데, 마지막 인풋 테스트 케이스에서 오답이 발생하는데요!? 이후에 강사님 풀이를 보고 조건 하나가 빠져서 오답이 발생했다는 것은 알았는데, 왜 오답이 발생하는지에 대해서는 잘 모르겠어서요.. 인풋이 워낙 큰 값이어서 디버깅하기가 힘드네요..
우선 마지막 인풋 테스트 케이스는
input: 7 8945
output: 1790
인데요!
제가 처음에 작성한 코드는 아래 코드인데요! 선생님 풀이를 본 후 추가시킨 if 문이 주석 처리 해준 부분입니다.
왜 제 풀이로 하면 마지막 인풋에 대해서 1063이라는 아웃풋이 나오게 될까요..? 근본적인 이유가 궁금하네요..
s, e = map(int, input().split())
move = [1, -1, 5]
MAX = int(1e4)
distance = [-1] * (MAX+1)
distance[s] = 0 # 출발지점 거리 0으로 초기화
queue = deque([s])
while queue:
pos = queue.popleft()
if pos == e:
break
# 3가지 방법으로 이동
for m in move:
#if 0 < pos + m <= MAX: # 이 조건이 없으면 마지막 인풋 오답나옴
if distance[pos + m] == -1: # 방문한 곳 아니라면!
distance[pos + m] = distance[pos] + 1
queue.append(pos + m)
print(distance[e])
답변을 작성해보세요.
0
답변 1