[python] 9095. 1, 2, 3 더하기

 

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

 

풀이

 

이번 문제도 DP 문제입니다.

DP의 핵심은 점화식을 찾는 것인데, 쉽사리 점화식이 잘 보이지 않았던 문제입니다.

 

하지만 여러 문제를 풀어보고 나니, 

'1, 2, 3' 이게 하나의 힌트가 될 수 있음을 알게되었습니다. 

 

오늘도 문제 풀이의 과정은 이해가 쉽도록 그림을 첨부하겠습니다 !

 

 

 

위의 그림처럼 n이 1일 때, 2일 때, 3일 때

이렇게 순차적으로 정답을 생각해보면 좋습니다.

 

n이 4일 때는 (n이 3인 경우 + 1), (n이 2인 경우 + 2), (n이 1인 경우 + 3) 임을 알게되었습니다.

이렇게 점화식을 찾았으면, 코드를 작성하는 건 어렵지 않습니다 ^.^ ! 

 

코딩 고수가 되고싶네요 ...

자 이제 코드를 보겠습니다 ~ 

 

 

cnt = int(input())
dp = [0 for i in range(11)]

dp[1] = 1
dp[2] = 2
dp[3] = 4

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

for _ in range(cnt):
    n = int(input())
    print(dp[n])