[Python 3] BOJ 15991: 1, 2, 3 더하기 6

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

 

일반적인 DP 문제이다.

두 개의 list를 정의하였는데, dp[n]는 1,2,3의 합으로 n을 만들 수 있는 모든 경우의 수를 정의하고, answer[n]은 대칭적으로 n을 만들 수 있는 경우의 수, 즉 문제의 정답을 의미한다.

예를 들어,

1 -> dp[1]= 1

1+1 , 2 -> dp[2]= 2

1+1+1, 1+2, 2+1, 3 -> dp[3]=4 와 같이 정의되고, 

 

1 -> answer[1]= 1

1+1, 2 -> answer[2] =2

1+1+1, 3 -> answer[3] =2

1+1+1+1, 2+2, 1+2+1 -> answer[4]=3 와 같이 정의된다.

 

여기서, dp[i]의 값은 dp[i-1], 1 의 조합, dp[i-2], 2 의 조합, dp[i-3], 3의 조합으로 이루어진다.

따라서, dp[i]= dp[i-1] + dp[i-2] + dp[i-3]으로 정의될 수 있다.

또한 answer[i]의 값은 서로 대칭적으로 합을 만들어야하므로, 

i가 홀수인 경우와 짝수인 경우로 나뉘어지는데,

i가 홀수인 경우 dp[(i-1)//2] ,  1, dp[(i-1)//2]의 형태와 dp[(i-3)//2], 3, dp[(i-3)//2] 의 형태로 만들어지고,

i가 짝수인 경우인 경우 dp[(i-2)//2], 2, dp[(i-2]//2]의 형태와 dp[i//2],dp[i//2]의 형태로 만들어진다.

즉, 가운데 있는 숫자가 1(ex.1321231)과 3(ex. 12321)으로 대칭되는 경우, 가운데 숫자가 2(13231)거나 없는 경우 (ex. 123/321)로 정의될 수 있다.

t=int(input())
maxnumber=100001
mod=1000000009
dp=list(0 for _ in range(maxnumber))
answer=list(0 for _ in range(maxnumber))
dp[1]=1
dp[2]=2
dp[3]=4
answer[1]=1
answer[2]=2
answer[3]=2
for i in range(4,maxnumber):
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
    dp[i]%=mod
    if not i%2:
        answer[i]=dp[i//2]+dp[(i-2)//2]
    else:
        answer[i]=dp[(i-1)//2]+dp[(i-3)//2]
for _ in range(t):
    n=int(input())
    print(answer[n]%mod)