9095번 Python

import sys

cnt = int(sys.stdin.readline())
dp = [0] * 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 i in range(cnt + 1):
    n = int(sys.stdin.readline())
    print(dp[n])

코드부터 구성하자면 다음과 같이 구성했다.

 

1 -> 1 # 1
2 -> 1 + 1, 2 # 2
3 -> 1 + 1 + 1, 1 + 2, 2 + 1, 3 # 4

많은 사람들이 블로그에 올린 걸 보면 1, 2, 3번째 인덱스에 왜 1, 2, 4를 넣는지 잘 모르는 것 같다. 문제에서 합을 나타날 때는 1개 이상의 수를 사용하라고 적혀있다. (사실 이걸 못보고 1을 0으로 했다가 애먹었다.) 그렇기 때문에 1을 만들 수 있는 경우는 1, 2는 2은 4가 된다. 

 

여기서 4는 7이라고 나와있는데 이는 1, 2, 3의 인덱스를 모두 더한 것과 같다.

 

'1 + 1 + 1' + 1
'1 + 2' + 1
'2 + 1' + 1
'3' + 1
'1 + 1' + 2
'2' + 2
'1' + 3

''로 표시한 부분이 전부 1, 2, 3에 해당하는 해를 의미한다. 단순히 거기에 숫자만 더해줬을뿐 실제로는 i 아래의 3개 인덱스를 모두 더한 것이 결국 점화식이 된다.