15990 백준 파이썬

 

15988과 거의 유사한 문제, 다만 연속해서 사용할 수 없다는 것이 차이점이다.

 

https://0422.tistory.com/71

15988 백준 파이썬

 

dp는 역시 나열이다. 1부터 6까지 나열해 보자.

 

1	2	3	4	5	6
1	2	1+2 2+1 3	1+2+1 1+3 3+1	1+3+1 2+1+2 2+3 3+2	1+2+1+2 1+2+3 1+3+2 2+1+2 2+1+3 2+3+1 3+1+2 3+2+1

 

사실 나는 8까지 나열해 봤지만, 뭔가 식으로 일반화 할 수 가 없어서 그만뒀다. 

그러나 뭔가 규칙을 발견 할 수는 있었다.

어떤 수의 나열 중 1로 시작하는 나열은 이전 수의 2와 3으로 시작하는 나열의 갯수의 합과 동일한 수를 가진다는 것

예를 들어 6의 경우

1+로 시작하는 나열은 5의 2+와 3+로 시작하는 나열의 수와 같은 수를 가진다.

동일하게 2로 시작하는 수는 4의 1+와 3+로 시작하는 나열의 수와 같은 수를 가지고,

3은 +의 1+와 2+와 같은 수를 가지게 된다.

 

따라서 간단하게 만들면

T(k)=T(k-1)의 2로 시작하는 것 + T(k-1)의 3으로 시작하는 것 + T(k-2)의 1로 시작하는 것 + T(k-2)의 2로 시작하는 것 + T(k-3)의 1으로 시작하는 것 + T(k-3)의 2로 시작하는 것

으로 나타 낼 수 있다.

 

그렇다면 우리가 리스트에 저장해야 할 것은 각 수의 1,2,3으로 시작하는 나열의 갯수이다.

그리고 출력은 1,2,3으로 시작하는 나열의 갯수의 합을 구해 보여주면 되겠다.

15988과 동일하게 나머지를 먼저 계산하여 저장해야 메모리초과가 뜨지 않고, 시간을 단축할 수 있다.

 

따라서 코드는 아래와 같다.

import sys
input=sys.stdin.readline
r=1000000009
dp=[[0,0,0],[1,0,0],[0,1,0],[1,1,1]]
ans=[0 for x in range(100001)]
for k in range(3,100001):
        dp.append([(dp[k][1]+dp[k][2])%r,(dp[k-1][0]+dp[k-1][2])%r,(dp[k-2][0]+dp[k-2][1])%r])
for k in range(100001):
    ans[k]=(dp[k][0]+dp[k][1]+dp[k][2])%r
t=int(input())
for _ in range(t):
    x=int(input())
    print(ans[x])