[python] 백준 1670 정상 회담2

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

1670번: 정상 회담 2

문제 해결

• 원 안에서 짝을 짓는 것을 할 때는 보통 한 사람을 기준으로 하게 된다.
• 그 한사람이 짝을 이뤘을 때를 생각한다. (짝은 무조건 이루어진다.)
• 그러면 반이 나눠지는데 양쪽 모두 국가가 짝수개가 있어야한다.
• 그 개수가 j개 ,(n-2-j)개라고 하자. 그리고 (j<n-2-j 라고 하자)
• 그러면 j는 0, 2, ... <n//2-1 가 된다.
• 이 부분을 DP를 이용해서 해결한다.
• 만약 반땅이 되는 경우 (n%4==2 (2는 기준점과 그 반대쪽에 있는점 2개) 이으면 j==n-2-j이다. 이 경우 dp[n] += dp[j]*dp[j]이다.

 

CODE

mod = 987654321
dp = [0]*10001
n = int(input())
dp[0] = 1
dp[2] = 1
dp[4] = 2*dp[2]
for i in range(6,n+1,2):
    total = 0
    for j in range(0,i//2-1,2):
        total += dp[j]*dp[i-j-2]*2
    if (i%4==2):
        total += dp[(i-2)//2]*dp[(i-2)//2] # 반갈
    dp[i] = total%mod
print(dp[n])