백준 :: 1, 2, 3 더하기 5 <15990번>

혜 콩·2022년 8월 16일
0

알고리즘

목록 보기
47/61

> 문제 <

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

> 풀이 <


dp[i][S] : i (총합 수) , S (끝자리 숫자)
→ dp[i][0] = 끝자리가 1인 합의 갯수, dp[i][1] = 끝자리가 2인 합의 갯수 ...
dp[i-1]의 끝자리가 2나 3일 때 (1이면 불연속 조건 미충족), 뒤에 +1만 하면 되는거니까, 갯수는 동일
dp[i][0] = dp[i-1][1] + dp[i-1][2]
dp[i-2]의 끝자리가 1이나 3일 때, 뒤에 +2 (dp[i]의 끝자리가 2가 되는 경우)
dp[i][1] = dp[i-2][0] + dp[i-2][2]
dp[i-3]의 끝자리가 1이나 2일 때, 뒤에 +3 (dp[i]의 끝자리가 3이 되는 경우)
dp[i][2] = dp[i-3][0] + dp[i-3][1]

> 코드 <

T = int(input())

dp = [[0] * 3 for _ in range(100001)]
# 1, 2, 3으로 끝난 갯수 세기 (1, 2, 3) --> 3 = [1+2, 2+1, 3]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    dp[i][0] = dp[i-1][1] % 1000000009 + dp[i-1][2] % 1000000009      # +1 해야하는데 연속으로 1이 나오면 안되니까, 이전 dp에서 2랑 3인 경우만 +  
    dp[i][1] = dp[i-2][0] % 1000000009 + dp[i-2][2] % 1000000009
    dp[i][2] = dp[i-3][0] % 1000000009 + dp[i-3][1] % 1000000009


for _ in range(T):
    n = int(input())
    print(sum(dp[n]) % 1000000009)
profile
배우고 싶은게 많은 개발자📚

0개의 댓글