[Python] 백준 15988 1, 2, 3 더하기3

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

15988번: 1, 2, 3 더하기 3

 

코드 작성

dp = [0] * 1000001
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, 1000001):
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009
t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n]%1000000009)

코드  풀이

#1

위 방법 처럼 각 숫자를 나타낼 수 있는데

 

4의 값을 표현하는 방법은

3의 표현에 더하기 1

2의 표현에 더하기 2

1의 표현에 더하기 3

 

5의 값을 표현하는 방법은

4의 표현에 더하기 1

3의 표현에 더하기 2

2의 표현에 더하기 3

 

점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이다.

 

 

#2

n의 범위는 100만개까지 가므로 많은 용량이 필요하는데

dp값을 먼저 설정하고

입력값 n에 대해서 for문을 돌려야 된다. 아래와 같은 코드로 작성 할 경우 시간초과

 

#3

dp[0]에서 0을 나타내는 방법은 1,2,3으로 나타내지 않는 방법이므로 1개가 된다.

n = int(input())
for _ in range(n):
    dp = [0] * (1000001)
    num = int(input())
    dp[1] = 1
    dp[2] = 2
    dp[3] = 6
    for i in range(4,1000001):
        dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009
    print(dp[num]%1000000009)