[Baekjoon/Python] 백준: 15990 1, 2, 3 더하기 5

 

 

다이나믹 프로그래밍 (DP) 문제입니다.

사실 간단해 보이는 문제였지만, 같은 수를 두 번 이상 연속해서 사용해서는 안된다.

라는 조건이 있어서 생각보다는 쉽지 않았던 문제입니다.

 

 

마지막에 어떤 수를 배열했는지만 알면, 숫자가 연속되는 것을 막을 수 있다는 것만 활용하면 금방 풀리는 문제였습니다.

	1	2	3
마지막이 1	1	0	1 => 2 + 1
마지막이 2	0	1	1 => 1 + 2
마지막이 3	0	0	1 => 3

 

이런식으로 마지막이 어떤 숫자로 끝나는 지에 따라 dp 배열을 달리 했습니다.

 

 

그러면 그 다음 4부터는 어떻게 구하면 될까요?

 

 

이런식으로 규칙을 찾아냈습니다.

dp[2][4] = dp[1][2] + dp[3][2] 이므로 0입니다.

 

 

import sys
input = sys.stdin.readline
dp = [[0] * (100_001) for _ in range(4)]
dp[1][1] = 1; dp[2][2] = 1; dp[1][3] = 1; dp[2][3] = 1; dp[3][3] = 1
for i in range(4, 100001):
    dp[1][i] = (dp[2][i-1] + dp[3][i-1]) % 1_000_000_009
    dp[2][i] = (dp[1][i-2] + dp[3][i-2]) % 1_000_000_009
    dp[3][i] = (dp[1][i-3] + dp[2][i-3]) % 1_000_000_009
t = int(input())
for tc in range(t):
    n = int(input())
    print((dp[1][n] + dp[2][n] + dp[3][n]) % 1_000_000_009)

 

위에서 구한 규칙을 통해 점화식을 만들고 dp 배열을 채워준 뒤,

각각의 테스트 케이스에서 입력받은 n값에 따라 해당 dp배열을 불러왔습니다.

그리고 조건에 따라 1,000,000,009 로 나눈 나머지값을 구해주었습니다.

 

0의 개수가 많아지면 코드를 짜는 입장에서 헷갈리는 경우가 많기 때문에

3자리마다 언더바로 끊어서 자리수를 표시해줬습니다.