[백준 파이썬] 9095 1,2,3 더하기

📌문제 출처

솔브닷 3+ 클래스 단계
https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

❓ 문제

❗ 풀이

• dp 활용

📗 풀이 코드

import sys
input = sys.stdin.readline
dp = {0:1,1:1,2:2}
for i in range(3,12):
    dp[i]=dp[i-3]+dp[i-2]+dp[i-1]
for _ in range(int(input())):
    print(dp[int(input())])

📗 코드 해설

• 해당 문제는 하나씩 수열을 늘려가다보면 점화식은 금방 찾을 수 있다.
  dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
• 해당 점화식으로 문제는 쉽게 풀 수 있지만 대체 왜 이런 식이 성립하는지 찾기까지 오래걸렸다.
• 아래 그림을 통해 왜 저런 점화식이 성립하는지 알아보자
  
• 위의 그림과 같이 dp[4]는 dp[1],dp[2],dp[3]의 경우의 수를 합한만큼의 경우의 수가 나온다.
• 이때 dp[1]의 뒤에 3을 더하는 경우에서 1+3과 3+1의 조합이 발생하는 것으로 셀 수도 있지만,
  이는 dp[3]의 뒤에 1을 더하는 경우와 중복이 되므로, 각 dp의 맨 뒤에 1,2,3을 더하는 경우로 세주면
  중복을 배제하고 경우의 수를 세줄 수 있다.