[백준] 1463 - 1로 만들기

아이데이션

이렇게 문제를 딱 봤을 때, 1차원 배열이 머릿속에 그려지고 징검다리 퐁퐁(?) 건너는 듯한 문제는
보통 그래프(DFS/DBF) 나 다이나믹 프로그래밍으로 풀리는 경우가 많았다

이 문제는 그래프보다는 다이나믹 프로그래밍으로 풀어야 한다고 생각했는데 이유는 다음과 같다

1. 주어진 숫자가 계속해서 감소하기만 한다

더하는 연산이 없기 때문에 한번 감소하면 다시 증가할 수 없다.
즉 숫자의 변화가 한 방향으로만 계속 된다.

만약 중간에 증가하는 연산이 있다면, 타겟값을 찾을 때까지 숫자들이 계속 연결되는 그래프 형태를 띄기 때문에
그래프 형태로 문제를 푸는 것이 맞다

2. 최솟값을 찾는다

이건 꼭 다이나믹 프로그래밍 만의 특성이라고는 볼 수 없지만!!
아무튼 다이나믹 프로그래밍 문제에서 많이 나오는 조건이여서 넣었다

 

풀이

n = int(input())
cache = [int(1e9)] * (n + 1)
cache[n] = 0

for i in range(n, 0, -1):
    if(i % 3 == 0):
        cache[i // 3] = min(cache[i // 3], cache[i] + 1)
    if(i % 2 == 0):
        cache[i // 2] = min(cache[i // 2], cache[i] + 1)
    if(i > 0):
        cache[i - 1] = min(cache[i - 1], cache[i] + 1)

print(cache[1])