[백준] 15990: 1, 2, 3 더하기 5 (Python)

문제📖

풀이🙏

• 1차원 dp테이블을 이용해서 구하기에는 많이 어려웠다.
• 2차원 dp테이블을 이용해서 1, 2, 3으로 끝나는 경우를 구분한다.
• dp[i][0] = (dp[i-1][1])%MOD + (dp[i-1][2]) % MOD의 경우 2, 3으로 끝나는 숫자에 1을 더해서 새로운 테이블을 갱신한다.
• dp[i][1] = (dp[i-2][0])%MOD + (dp[i-2][2]) % MOD의 경우 1, 3으로 끝나는 숫자에 2을 더해서 새로운 테이블을 갱신한다.
• dp[i][2] = (dp[i-3][0])%MOD + (dp[i-3][1]) % MOD의 경우 1, 2으로 끝나는 숫자에 3을 더해서 새로운 테이블을 갱신한다.
• 구하고자 하는 값을 sum(dp[n])을 통해 출력한다.

코드💻

MOD = 1000000009
dp = [[0] * (3) for _ in range(100001)]
dp[1] = [1, 0, 0] # 1로 끝나는 경우
dp[2] = [0, 1, 0] # 2로 끝나는 경우
# 2+1 : 1로 끝나는 경우
# 1+2 : 2로 끝나는 경우
# 3 : 3로 끝나는 경우
dp[3] = [1, 1, 1] 
for i in range(4, 100001):
    # 2, 3으로 끝난 숫자에 1 더하기
    dp[i][0] = (dp[i-1][1])%MOD + (dp[i-1][2]) % MOD 
    # 1, 3으로 끝난 숫자에 2 더하기
    dp[i][1] = (dp[i-2][0])%MOD + (dp[i-2][2]) % MOD
    # 1, 2으로 끝난 숫자에 3 더하기
    dp[i][2] = (dp[i-3][0])%MOD + (dp[i-3][1]) % MOD

for _ in range(int(input())):
    x = int(input())
    print(sum(dp[x])%MOD)