[골드 3] 백준 1670 - 정상 회담 2 (파이썬)

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

풀이

• 사람 수는 짝수 N이고, 각 사람은 한 명과만 악수할 수 있으며, 악수 선이 교차하지 않아야 한다.
• 이는 DP로 해결할 수 있으며, 다음 점화식을 따른다.

이 문제는 카탈란 수(Catalan Number) 문제 유형의 대표적인 예다.

핵심은 다음과 같다

• N명의 정상 중 한 명을 기준으로 짝을 지었을 때, 남은 좌우 인원들도 각각 교차 없이 짝을 지어야 한다.
• 이를 이용하면 DP 점화식을 다음과 같이 세울 수 있다.

D[0] = 1  # 아무도 없을 때는 1가지 (아무것도 안 하는 경우)
D[2] = 1  # 두 명이 있을 때는 1가지

D[n] = D[0]*D[n-2] + D[2]*D[n-4] + D[4]*D[n-6] + ... + D[n-2]*D[0]

즉, D[n]은 n명이 있을 때의 가능한 짝짓기 경우의 수이고, 각 항은 첫 번째 사람과 짝을 지은 이후 좌우로 나뉜 그룹들의 경우의 수를 곱해서 누적한 것이다.

코드

# 백준 1670 - 정상회담 2
# 분류 : 다이나믹 프로그래밍

N = int(input())
mod = 987654321

D = [0] * (N + 1)
D[0] = 1

for i in range(2, N + 1, 2) :
    D[i] = 0
    for j in range(0, i - 1, 2) :
        D[i] += D[j] * D[i - 2 - j] % mod
        D[i] %= mod

answer = 0
for i in range(0, N - 1, 2) :
    answer += D[i] * D[N - 2 - i] % mod
    answer %= mod

print(answer)