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

Python3,DP

문제

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

입출력

입출력 예시

키워드

• DP

주요 포인트

정수 n은 양수이며 11보다 작다.

1일 때, 1 -> 1
2일 때, 1+1 | 2 -> 2
3일 때, 1+1+1 | 2+1 | 1+2 | 3 -> 4
4일 때, 1+1+1+1 | 1+2+1 | 2+1+1 | 1+1+2 | 2+2 | 3 -> 7

1일 때 + 2일 때 + 3일 때 = 4일 때
즉, dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 로 표현할 수 있다

최종 코드

t = int(input())
dp = [0] * 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(t):
    n = int(input())
    print(dp[n])

피드백

DP 문제는 확실히 수학 문제 풀이 같다
반복되는 규칙을 찾는 게 포인트인데 너무 국지적으로 보지말고 앞뒤 관계랑 숫자를 따져 가면서 찾는 게 필요하다.