백준 9095: 1, 2, 3 더하기 해설- python

✏️ 문제

9095번: 1, 2, 3 더하기

9095

✏️ 풀이

늘 그렇듯 규칙을 찾아보자. 

 

n=1 일 때, 1n=2 일 때, 1+1, 2n=3 일 때, 1+1+1, 1+2, 2+1, 3n=4 일 때, 1+1+1+1, 1+3, 3+1, 4....어? 이거다. 1+3은 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3). 아까 n=3일 때 해결한 문제를 내포하고 있다.즉 n이 3보다 커지면 그 문제들은 n=1,2,3일 때의 문제를 포함하고 있다.즉 작은 문제(n=1,2,3)를 이용해 큰 문제를 해결하는 동적계획법(Dynamic Programming)을 이용하면 적합하겠다.

 

[Python & Algorithm] Dynamic Programming(동적프로그래밍)

 

n=4 문제의 방법의 수를 cache[4]라고 정의하겠다. 그러면 위에서 알아보았듯

cache[1] = 1

cache[2] = 2

cache[3] = 4 가 될 것이다.

 

점화식을 작성하기 위한 규칙성은 어떤가?

cache[4]는 cache[3]에 +1을 한 것, cache[2]에 +2를 한 것, cache[1]에 +3을 한 것을 모두 합한 것이다.

따라서 점화식은 cache[n]=cache[n-1]+cache[n-2]+cache[n-3]이 될 것이다.

 

(Python)

cache = [0]*11
cache[1]=1 # 1
cache[2]=2 # 1+1,2
cache[3]=4 # 1+1+1+1,1+3,3+1,2+2

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

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