[python/파이썬] 백준 15990 1, 2, 3 더하기 5

[문제 출처]

https://www.acmicpc.net/problem/15990

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

 

 

[문제 풀이]

 

 

9095번 문제인 '1, 2, 3 더하기'와 유사하지만 15990번 문제는 9095번과는 달리 2차원 배열을 사용하여 해결하는 문제이다.

 

1,2,3 이 세 가지의 숫자를 사용하되 연속적으로는 사용할 수 없다.

따라서 n에 대한 답을 알기 위해서는 n행 3열짜리 리스트가 필요하다.

 

기본적인 규칙은 간단하다.

dp[n][0]에는 n을 나타내는 방법중에 마지막 숫자가 1로 끝나는 경우의 수를 저장한다.

dp[n][1]에는 n을 나타내는 방법중에 마지막 숫자가 2로 끝나는 경우의 수를 저장한다.

dp[n][2]에는 n을 나타내는 방법중에 마지막 숫자가 3으로 끝나는 경우의 수를 저장한다.

 

연속적으로 같은 수를 사용할 수 없기 dp[n][0] 뒤에는 2 혹은 3을 배치한다.

같은 방식으로 dp[n][1] 뒤에는 1, 3

dp[n][2] 뒤에는 1,2만 올 수 있다.

 

이런 규칙을 사용하면 

dp[n][0]은 1로 끝나야 하므로 n보다 1작은 수인 n-1의 dp값중에 2와 3으로 끝나는 경우의 합을 저장한다.

dp[n][1]은 2로 끝나야 하므로 n보다 2작은 수인 n-2의 dp값중에 1과 3으로 끝나는 경우의 합을 저장한다.

dp[n][2]은 3로 끝나야 하므로 n보다 3작은 수인 n-3의 dp값중에 1과 2로 끝나는 경우의 합을 저장한다.

 

결론은 이런 규칙을 따른다.

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

 

그리고 n에 대한 경우의 수는 위의 세 값의 합이 된다.

import sys
input = sys.stdin.readline


T = int(input())

dp = [[0 for _ in range(3)] for i 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][2] + dp[i-2][0])%1000000009
    dp[i][2] = (dp[i-3][0] + dp[i-3][1])%1000000009 
	#나머지를 저장하지 않으면 값이 너무 커져 시간초과가 뜸

for j in range(T):
    n = int(input())
    print(sum(dp[n])%1000000009)
    #마지막에도 나머지 연산을 해줘야 틀리지 않음

 

 

[유사한 문제]

 아래의 문제를 풀어보지 않았다면 먼저 풀어보고 이번 문제를 풀면 좋을 것 같다.

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

[9095번 문제 풀이 링크]

https://sodehdt-ldkt.tistory.com/63

[python/파이썬] 백준 9095 1, 2, 3 더하기