[Python] 백준 / silver / 1463번 (1로 만들기)

문제 링크 : https://www.acmicpc.net/problem/1463
아이디어 출처 : [이것이 코딩테스트다] 책

이 문제를 그리디 알고리즘으로 착각했었다. 나랑 비슷하게 착각한 사람이 많을 것 같다. 왜냐하면 이 문제랑 비슷한 많은 문제들이 그리디로 풀리기 때문이다,,

반례 10 = 10 -> 9 -> 3 -> 1 을 보고, Dynamic Programming 이라고 깨닫고 문제를 풀긴 했는데, 어쩔때 그리디 알고리즘이 써먹히고 어쩔때 DP로 풀어야 하는지 정확히 해둬야 할 것 같다.

그리디 알고리즘은 내가 계획한 탐욕법이 끝까지 반례가 없어야 한다는 가정하에 작성해야한다. 예를 들어, 유명한 그리디 문제 "거스름 돈" 문제를 떠올려보면 좋다.

거슬러줄 수 있는 동전이 [500, 100, 50, 10]원 짜리를 갖고 있을 경우 이 문제는 그리디 알고리즘을 적용해 풀 수 있다.

왜냐하면 큰 단위 동전이 항상 작은 단위 동전의 배수 형태 이기 때문이다. 그래서 매 판단 때 큰 동전 먼저 처리하는 탐욕법이 알맞는 것이다.

다른 예를 들어, 거슬러 줄 수 있는 동전이 [500, 400, 100]원 짜리 일 경우, 800원을 거슬러줘야 한다고 생각해보자. 그리디 알고리즘으로는 500 + 100 + 100 + 100 -> 4개를 거슬러주는 결과가 나오지만, 사실 400 + 400 -> 2개로도 거슬러 줄 수 있다. 이런 결과가 나오는 이유는 동전들이 배수 관계가 아니기 때문이다.

결론적으로, 그리디 알고리즘을 계획 할 때는 내가 짠 로직이 반례가 없는지 반드시 검토할 수 있어야 한다.
반례가 존재할 경우엔 다이나믹 프로그래밍을 고려해보는 것이 좋을 것 같다.

정답 코드

import sys
N = int(sys.stdin.readline())

if N == 1:
    print(0)
    exit(0)
elif N == 2 or N == 3:
    print(1)
    exit(0)

dp = [0]*(N+1)
dp[1] = 0
dp[2] = 1
dp[3] = 1

for i in range(4, N+1):
    if i % 3 == 0 and i % 2 == 0:
        dp[i] = min(dp[i-1], dp[i//2], dp[i//3]) + 1
    elif i % 3 == 0:
        dp[i] = min(dp[i-1], dp[i//3]) + 1
    elif i % 2 == 0:
        dp[i] = min(dp[i-1], dp[i//2]) + 1
    else:
        dp[i] = dp[i-1] + 1

print(dp[N])