[문제 풀이] 백준 1463

해결 과정

그리디 인가 싶어서 3을 나누고, 2를 나누고, 1을 빼는 순서로 했는데 이게 아니었다. 

분류가 다이나믹 프로그래밍. 다른 풀이를 참고했다.

나의 풀이

X = int(input())
dp = [0] * (X+1)
for i in range(2, X+1):
    dp[i] = dp[i-1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
print(dp[X])

다른 풀이

이 분 블로그 글 참고

 

IDEA