15993번: 1, 2, 3 더하기 8
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
www.acmicpc.net
코드
dp = [[0]*2 for _ in range(100001)] # 홀수, 짝수
dp[1][0] = 1
dp[2][0] = 1
dp[2][1] = 1
dp[3][0] = 2
dp[3][1] = 2
for i in range(4, 100001):
dp[i][0] = (dp[i-1][1]+dp[i-2][1]+dp[i-3][1]) % 1_000_000_009
dp[i][1] = (dp[i-1][0]+dp[i-2][0]+dp[i-3][0]) % 1_000_000_009
for _ in range(int(input())):
n = int(input())
print(*dp[n])
dp[i]에는 [홀수 개의 수를 더한 경우의 수, 짝수 개의 수를 더한 경우의 수]가 저장된다. 그러므로 dp[i][0]과 dp[i][1]의 값을 구할 때는 i-1에서 +1을 한 경우의 수, i-2에서 +2를 한 경우의 수, i-3에서 +3을 한 경우의 수를 더해서 구해주면 된다. 이때 0열의 값은 짝수개의 수로 만드는 경우를 저장하는 것이므로 i-1, i-2, i-3 모두 1열에서 갖고 와야 하고, 1열의 값은 그 반대이다. 말은 어렵지만 코드의 8~9번째 줄을 보면 이해할 수 있을 것이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 14430번 자원 캐기 (2) | 2024.04.27 |
---|---|
[Python/파이썬] 백준 21923번 곡예 비행 (0) | 2024.04.26 |
[Python/파이썬] 백준 2157번 여행 (0) | 2024.04.24 |
[Python/파이썬] 백준 1757번 달려달려 (0) | 2024.04.09 |
[Python/파이썬] 백준 2670번 연속부분최대곱 (0) | 2024.04.04 |