greentea31's Note

https://www.acmicpc.net/problem/1463

풀이 과정

3으로 나누어 보고 안되면 2로 나누고, 안되면 1을 빼보고 하는 그리디 방식이 문제를 보자마자 떠오르겠지만, 그리디 방식으로 풀면 답이 나오지 않는 예제를 힌트에서 주었다

D[N]을 숫자 N을 1로 만들기 위해 필요한 연산의 최소 수라고 하자. 그러면 아래와 같은 점화식이 성립한다

1. N이 2와 3으로 모두 나누어 떨어진다면

    D[N] = min(D[N/3], D[N/2], D[N-1]) + 1

2. N이 3으로만 나누어 떨어진다면

    D[N] = min(D[N/3], D[N-1]) + 1

3. N이 2로만 나누어 떨어진다면

    D[N] = min(D[N/2], D[N-1]) + 1

4. N이 2와 3으로 나누어 떨어지지 않는다면

    D[N] = D[N-1] + 1

점화식을 코드로 구현해 문제를 해결할 수 있다.

소스 코드

d = [0] * 1000001
N = int(input())

for i in range(2, N+1):
    d[i] = d[i-1] + 1
    if i % 3 == 0:
        tem = d[i//3] + 1
        if tem < d[i]:
            d[i] = tem
    if i % 2 == 0:
        tem = d[i//2] + 1
        if tem < d[i]:
            d[i] = tem

print(d[N])