[Python] 9095번 1, 2, 3 더하기

✏️ 문제

 

문제 파악

직접 넣어보면 다음과 같이 나온다. 

n	dp(n)	개수
1	dp(1)	1
2	dp(2)	2
3	dp(3)	4
4	dp(4)	7
5	dp(5)	13

 

위의 표를 보면

• dp(n)일 때, 개수 =  dp(n-1) + dp(n-2) + dp(n-3)

라는 규칙이 있다는 것을 알 수 있다.

이 점화식을 활용하여 코드를 짜면 쉽게 풀 수 있다! 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

t = int(input())
dp = [0, 1, 2, 4]

for i in range(4, 12):
  dp.append(dp[i-1] + dp[i-2] + dp[i-3]) 

for i in range(t):
  n = int(input())
  print(dp[n])