[BOJ_15990] 1, 2, 3 더하기 5

문제를 해결하기 위한 점화식을 구하려면 2차원 dp를 만들어야 합니다.

 

dp[n][1] = dp[n-1][2] + dp[n-1][3]

dp[n][2] = dp[n-2][1] + dp[n-2][3]

dp[n][3] = dp[n-3][1] + dp[n-3][2]

 

n을 만들기 위한 방법의 수 중 1로 끝나는 경우를 dp[n][1]이라고 합시다.

dp[n][1]은 ~~~ + 1 이런 식입니다.

dp[n-1][?] 의 경우 1로 끝날 수 없기 때문에 2나 3이 올 수 밖에 없기 떄문에 dp[n][1] = dp[n-1][2] + dp[n-1][3]가 성립합니다.

 

그리고 dp[n][2]의 경우 주의해야 할 점은

~~~ + 2로 끝났기 때문에 dp[n-2][?] 이 와야 한다는 점입니다.

 

※반복문 내부의 점화식에 %1000000009 를 안해주면 시간초과가 났습니다.

 

dp = [[0, 0, 0, 0] for i in range(100001)]
dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

for i in range(4, 100001):
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009
t = int(input())
arr = []
for _ in range(t):
	arr.append(int(input()))

for el in arr:
	print(sum(dp[el])%1000000009)

www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5