반응형
문제:
https://www.acmicpc.net/problem/15988
15988번: 1, 2, 3 더하기 3
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이:
- 해당 문제는 DP문제로 점화식을 구할 수 있다.
- n= 1, 2, 3, 4 까지 구해보면 dp(n) = dp(n-1) + dp(n-2) + dp(n-3) 임을 확인할 수 있다.
- n=4 까지의 dp변수에 리스트로 담아놓은 후 n=5부터 이 리스트로 구할 수 있다.
코드:
import sys
input = sys.stdin.readline
dp = [1, 2, 4, 7]
for i in range(int(input())):
n = int(input())
for j in range(len(dp), n):
dp.append((dp[-3]+dp[-2]+dp[-1])%1000000009)
print(dp[n-1])ex) n=7 일 때 range(len(dp), n) => 3번 반복
1번 반복 -> dp[-3] + dp[-2] + dp[-1] = 2 + 4 +7 =13 => dp=[1, 2, 4, 7, 13]
2번 반복 -> dp[-3] + dp[-2] + dp[-1] = 4 + 7 +13 =26 => dp=[1, 2, 4, 7, 13, 24]
3번 반복 -> dp[-3] + dp[-2] + dp[-1] = 7 + 13 + 26 =46 => dp=[1, 2, 4, 7, 13, 24, 44]
=> 답: 마지막 값인 dp[-1]=44 이다.
n=7일 때 dp 리스트 확인 :
반응형