[python] 백준 9095번 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

 

 

---

 

 

💻 코드

 

import sys

input = sys.stdin.readline

T = int(input())

d = [0] * 100

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

for _ in range(T):
    n = int(input())
    for i in range(4, n + 1):
        d[i] = d[i - 1] + d[i - 2] + d[i - 3]

    print(d[n])

 

 

 

📝 풀이

 

저번에 풀었던 2 X n 타일링 문제와 거의 같다. 푸는 방법은 똑같았고 점화식만 아주 살짝 바꿔주면 된다.

 

다이나믹 프로그래밍의 핵심이 같은 것이 반복되어 나오는 것이기 때문에 반복되는 것끼리의 연관을 잘 짓다 보면 쉽게 식을 구할 수 있다.

 

 

 

n이 1일 경우부터 5일 경우까지 쭉 써보았다. 주황색은 n - 1, 파란색은 n - 2, 초록색은 n - 3에 해당한다. 

예를 들어,  n이 4일 때 크게 3 + 1, 2 + 2, 1+ 3일 경우로 나누면 단순히 3의 경우의 수 + 2의 경우의 수 + 1의 경우의 수만 더하면 된다. 따라서 점화식은 d[i] = d[i - 1] + d[i - 2] + d[i - 3]이다.