[boj] 백준 9095 1, 2, 3 더하기 python 풀이

문제

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

9095번: 1, 2, 3 더하기

 

 

문제 풀이

dp 설명

 

위 그림처럼 4를 표현할때, 1+ 시작하는 값에서 1+를 떼고 보면 3을 표현하는 모든 방법의 수이다.

2+는 4-2 = 2를 표현하는 방법의 수이고, 3+는 4-3 = 1을 표현하는 방법의 수이다. 

정리하면, 4는 3을 표현하는 방법의 수 + 2를 표현하는 방법의수 + 1을 표현하는 방법의 수 이다.

(중복되는 값은 없음. 왜냐면 1+2+1 와 2+1+1 는 다른 방법으로 세야하니까)

 

이런식으로 i번째는 1+(i-1)번째의 표현 방법의 수 + 2+(i-2)수의 표현 방법 + 3+(i-3)의 표현 방법

dp로 표현하면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

코드

import sys
input = sys.stdin.readline

T = int(input().strip())
dp = [0 for _ in range(11+1)]
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,len(dp)):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

# print(dp)
for t in range(T):
    n = int(input().strip())
    print(dp[n])