[백준] 15989 1, 2, 3 더하기 4 - python

문제 링크

이 문제를 처음보고 뭔가 피보나치 수열 문제 풀 듯이 풀어야 할 것 같다는 생각이 들었다.
그런데..
피보나치랑은 조금 달라서 어떻게 해야 하나 고민이 되었다.
그래서 다른 블로그를 보면서 도움을 받았다.

일단 들어오는 숫자가 10000이하의 숫자이기 때문에 1~10000까지의 경우의 수를 모두 구한다.

2로 나타낼 수 있는 숫자는

for i in range(2, 10001):
    dp[i] += dp[i-2]

로 구했다.
예를 들어 1에서 2를 더하여 3을 만들 수 있으니까 dp[3]은 dp[1]이 가지고 있던 경우의 수를 더해주면 된다.
이를 10000까지 다 해주면 되는 것이다.

3으로 나타낼 수 있는 숫자도 마찬가지다.

for i in range(3, 10001):
    dp[i] += dp[i-3]

따라서 최종 코드는 아래와 같다.

#1,2,3 더하기 4
import sys

dp = [1] * 10001

for i in range(2, 10001):
    dp[i] += dp[i-2]

for i in range(3, 10001):
    dp[i] += dp[i-3]

n = map(int, sys.stdin.readline().rstrip())
for i in range(n):
    num = map(int, sys.stdin.readline().rstrip())
    print(dp[num])

다이나믹으로 푸는 문제는 늘 생각은 복잡하게 하는데, 풀이는 간단한 것 같다.
숫자가 작다면, 다 계산하는 것이 가장 좋은 방법인 것 같다.