[백준 - Python] 9095. 1, 2, 3 더하기 (DP)

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

9095번: 1, 2, 3 더하기

 

코드

T = int(input())

dp = [0 for _ in range(11)]
dp[1] = 1
dp[2] = 2
dp[3] = 4

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

for _ in range(T):
    n = int(input())
    print(dp[n])

 

방법의 수를 n이 1일 때부터 차례대로 적어가면서

숫자들 사이의 규칙을 찾아

점화식을 구하려고 시도를 했다.

 

N이 5인 경우에 대해서

경우의 수를 잘못 세고

내가 짐작한 점화식이 아닌 줄 알고 한참을 헤맸다.

 

5에 대한 방법의 수를 제대로 구하고 나서는

수월하게 문제가 풀렸다.

 

1, 2, 3을 이용해서 이들의 합으로 숫자를 표현하는 문제였다.

1, 2, 3은 직접 경우의 수를 세어보았고,

N이 4인 경우부터는

1인 경우에 3을 더하는 경우와

2인 경우에 2를 더하는 경우와

3인 경우에 1을 더하는 경우로 나누어 생각을 해보았다.

 

더해지는 3, 2, 1이 기존의 덧셈식에 어떤 순서로 더해지는 지를 적어보면서 점화식을 구해보려고 했다.

 

또한, 1, 2, 3을 이용해서 각 N에 대한 경우의 수를 구해야 함으로

i에 대한 점화식은 i-1, i-2, i-3인 경우에 종속적일 것이라고 생각하고 점화식을 구했다.