[백준 알고리즘] 9095번: 1, 2, 3 더하기 (Python / 파이썬)

문제 링크

9095번: 1, 2, 3 더하기

 

문제 접근

3을 만들 수 있는 경우의 수에서 1을 더한 것과

2를 만들 수 있는 경우의 수에서 2를 더한 것, 1을 만드는 경우의 수에서 3을 더한 것을 모두 합한다.

 

d[5]는 d[4] + d[3] + d[2] 로 정리할 수 있고, 이는 곧

d[n] = d[n-3] + d[n-2] + d[n-1] 이다.

 

11 이하인 수이므로 for문을 10회 반복한다.

 

정답 코드

import sys

X = int(sys.stdin.readline())

dp = [0] * (X + 1)

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

print(dp[X])