DP(다이나믹 프로그래밍): 백준 9095 파이썬 1,2,3 더하기

문제: 

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

9095번: 1, 2, 3 더하기

풀이:

이 문제를 풀면서 어떻게 점화식을 세워야 하는지에 대한 고민을 1시간 정도 했었는데 잘 떠오르지 않아 

결국 구글링을 했다.

규칙은 아주 간단했다. 점화식을 찾아서 해결하는 전형적인 DP문제였다.

• 1 -> (1),  1개
• 2 -> (1+1), (2) 2개
• 3 -> (1+1+1), (1+2), (2+1), (3) 4개
• 4 -> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), .... 7개
• 5 -> (1+1+1+1+1), .... 13개 

위의 규칙을 봤을 때, 정수 4를 1,2,3의 합으로 나타낼 수 있는 경우의 수는 총 7가지이다. 

이는 정수 1의 경우. 2의 경우, 3의 경우를 합한 결과와 같다는 것을 알 수 있다. 5의 경우도 마찬가지이다.

 

따라서 d[i] = d[i-1] + d[i-2] + d[i-3] (단,n > 3)의 점화식이 나온다. 이를 코드로 옮기면 정답이 된다.

 

정답:

import sys

n = int(sys.stdin.readline())
arr = [int(sys.stdin.readline()) for _ in range(n)]

d = [0] * 12

d[1] = 1
d[2] = 2
d[3] = 4


def dp(n):
    for i in range(4, n+1):
        d[i] = d[i-1] + d[i-2] + d[i-3]

    print(d[n])


for x in arr:
    dp(x)