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

문제

---

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

9095번: 1, 2, 3 더하기

 

 

 

풀이

---

d=[0]*11
d[1]=1
d[2]=2
d[3]=4

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

n = int(input())
for _ in range(n):
    m = int(input())
    print(d[m])

 

d[4]를 구해보자.

3을 만들 수 있는 경우의 수에서 +1을 한 것,

2를 만들 수 있는 경우의 수에서 +2를 한 것,

1을 만들 수 있는 경우의 수에서 +3을 한 것을 합치면된다.

즉, d[4] = d[3] + d[2] + d[1] 이라고 볼 수 있다.

 

d[5]는 d[4] + d[3] + d[2]가 된다. 

이렇게 구하다 보면

d[n] = d[n-3] + d[n-2] + d[n-1] 이라는 식이 나온다.

 

11 이하인 수 라고 했으므로 for문을 10까지 돌려주면 된다.