[CodingTest] BOJ9095 1,2,3 더하기 ( DP ) With 파이썬

9095번: 1, 2, 3 더하기

 

 

◎ 문제풀이

 

1,2,3 기저조건이 있고 목표값까지 가는 경우의 수를 구하는 문제이니 DP문제이다.  

 

 

 

 

 

1,2,3으로 10을 구하는 경우의 수를 d(10)이라고 하자.  10을 구하는 사건은 3가지 사건이 있다.

 

사건 ① : 9 + 1

사건 ② : 8 + 2

사건 ③ : 7 + 3

 

3가지 사건은 모두 독립사건이다. 그러므로 d(10) = d(9) + d(8) + d(7)이 성립된다.  dp는 기저조건으로 독립사건을 구하여 점화식을 도출하는 것이 중요하다. 

 

 

◎ 코드

n = int(input())

def dp(value) :
  d = [0]*11 
  d[1],d[2],d[3] = 1,2,4
  for i in range(4,value+1) :
    d[i] = d[i-3]+d[i-2]+d[i-1] 
  return d[value]
  
for _ in range(n) :
  print(dp(int(input())))