💡문제접근
- 규칙을 찾아서 점화식을 세워 문제를 해결하는 1차원 dp 테이블 문제로는 해결할 수 없었던 문제였다. 질문게시판을 찾아보니 2차원 dp 테이블을 이용해서 문제를 해결하는 코드가 상당히 많았다.
- N의 합을 구성하는 순서쌍 중에서 1로 끝나는 경우, 2로 끝나는 경우, 3으로 끝나는 경우로 나눈 후에 점화식을 세울 수 있다.
💡코드(메모리 : 51492KB, 시간 : 196ms)
import sys
input = sys.stdin.readline
dp = [[0 for _ in range(3)] for _ in range(100001)]
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] + dp[i-1][2]) % 1000000009
dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % 1000000009
dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % 1000000009
# 위의 dp 연산에서 1번의 나머지 연산만 이루어지지 않는 경우도 존재한다.
# 따라서, 아래에서 합계를 구할 때 역시 한 번 더 나머지 연산을 해줘야 한다.
T = int(input())
for _ in range(T):
n = int(input())
print(sum(dp[n]) % 1000000009)💡소요시간 : 40m
🐢