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

문제 설명

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

9095번: 1, 2, 3 더하기

---

문제 풀이

점화식 구하는 것에 익숙해지려고 쉬운 DP 문제부터 푸는 중 .. 

 

예시에 나온 D[4]를 봤을 때

1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1    => 3을 1, 2, 3의 합으로 나타내는 법 + 1

1 + 1 + 2, 2 + 2      => 2를 1, 2, 3의 합으로 나타내는 법 + 2

1 + 3       => 1을 1, 2, 3의 합으로 나타내는 법 + 3

 

점화식 : D[i] = D[i - 1] + D[i - 2] + D[i - 3]

초기값 : D[1] = 1, D[2] = 2, D[3] = 4

 

 

N이 입력될 때마다 매번 구해주기보다는

먼저 값을 다 구한 다음에 N이 들어오면 출력해주는 것이 훨씬 효율적이다

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(4, 12):
    d[i] = d[i - 1] + d[i - 2] + d[i - 3]

T = int(input())

for tc in range(T):
    n = int(input())
    print(d[n])