글 읽기 - 어느부분에서 틀린건지 도저히 찾지 못하겠습니다..

hope1213 2년 전 0

어느부분에서 이상한지 도저히 못찾겠습니다.. 반례를 모두 넣어봐도 맞다고 나와서 더욱 찾지 못하겠습니다 도와주세요..

from collections import deque

q = deque()

a,b = map(int,input().split())

q.append(a)

visited = [0]*100001
visited [a] = 1
li = [0]*100001

while q:
    v = q.popleft()
    
    if v * 2 < 100001 and visited[v*2]==0:
        visited[v*2]=1
        li[v*2] = li[v]
        q.append(v*2)
    if v + 1 < 100001 and visited[v+1]==0:
        visited[v+1]=1
        li[v+1] = li[v]+1
        q.append(v+1)
    if 0 <= v-1 and visited[v-1]==0:
        visited[v-1]=1
        li[v-1] = li[v]+1    
        q.append(v-1)

print(li[b])

sdh9615 2년 전 3

10일이 지나 댓글을 보실지 모르겠지만 져도 방금까지 겪던문제라 답변드립니다.

해당 코드로

시작지점 : 4, 도착지점 : 6 을 작성하게 되면 걸리는시간이 2초가 나옵니다 ( 4 - 5 - 6 ) 하지만 정답은 (4 - 3 - 6)으로 1초가 나와야합니다.

물론 단순하게 (*2, -1, +1) 순으로 검사하면 한번만 방문해서 값을 구할수 있지만

(*2, +1, -1) 순으로 검사해서 풀기위해선 여러번 방문해서 최소값의 초를 구해야합니다.

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

문제

문제

출처

ICPC

어느부분에서 틀린건지 도저히 찾지 못하겠습니다..

hope1213 2년 전 0

sdh9615 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말