글 읽기 - 목적지 + 1 이 최솟값이 되는 원리?(정답코드첨부)

superego0706 1년 전 0

이전에 18,26,39줄 코드에서 0 < cur_... <= dest + 1 부분의 dest + 1을 dest로 적어서 틀린적이 있습니다

목적지보다 작은 값에서 2배를 하는게 목적지를 초과해서 빼는것보다 더 효율적이라는 말을 기억해서 이렇게 짰었습니다.

일단 목적지 + 1 까지 2배를 하고 -1 하는것이 최솟값이 되는 반례를 보고 단순히 dest + 1로 바꿨더니 정답처리가 되었는데 이유를 모르겠네요

목적지의 값을 초과해서 -1 을 해야 최솟값이 보장되는 이유나 원리가 있을까요?

from collections import deque

start, dest = map(int, input().split())

def find(start, dest):
    visit = [0 for _ in range(dest + 2)]
    queue = deque()
    queue.append([start, 0])
    
    if start == dest:
        print(0)
    elif start > dest:
        print(start - dest)
    else:
        while queue:
            cur, cnt = queue.popleft()
            cur_pls, cur_mns, cur_twice = cur + 1, cur - 1, cur * 2
            while 0 < cur_twice <= dest + 1 and visit[cur_twice] == 0:
                if cur_twice == dest:
                    print(cnt)
                    return
                visit[cur_twice] = 1
                queue.append([cur_twice, cnt])
                cur_twice *= 2
                
            if 0 <= cur_pls <= dest + 1 and visit[cur_pls] == 0:
                if cur_pls == dest:
                    print(cnt + 1)
                    return
                else:
                    visit[cur_pls] = 1
                    queue.append([cur_pls, cnt + 1])
                    
            if 0 <= cur_mns <= dest + 1 and visit[cur_mns] == 0:
                if cur_mns == dest:
                    print(cnt + 1)
                    return
                else:
                    visit[cur_mns] = 1
                    queue.append([cur_mns, cnt + 1])
                    
find(start,dest)

zenith82114 1년 전 1

목적지를 초과한 다음 뒤로 후퇴하는 게 항상 비효율적인 건 아니죠.

말씀하신 대로 반례가 존재하니까요.

(예: 100에서 199까지 가는 경우 100->200->199가 100->99->198->199보다 빠름)

이것 말고도 얼마든지 더 있겠죠.

결국 출발지와 목적지 값에 따라

넘어가는 게 이득일 수도, 그러지 않는 게 이득일 수도 있는 거고

"목적지의 값을 초과해서 -1 을 해야 최솟값이 보장되는 이유나 원리가 있을까요?"라고 물으시면

"그런 케이스가 존재하니까요"라고 대답할 수밖에 없을 것 같습니다.

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

문제

문제

출처

ICPC

목적지 + 1 이 최솟값이 되는 원리?(정답코드첨부)

superego0706 1년 전 0

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말