[BOJ] 1670. 정상 회담 2

문제

---

전형적인 DP 문제이다.

포인트

---

f(2) = 1, f(4) = 2 이다. 이때 악수하는 한 사람을 포인트로 집었을 때 f(4) 에서 그 한 사람이 악수할 수 있는 사람은 양 옆 두 명이다. 따라서 f(4) = f(2) + f(2) 이다.

같은 원리로 f(6) 에서는 세 명과 악수할 수 있으며, 왼쪽, 오른쪽과 악수하면 4명이 남고, 가로질러 악수하면 양 옆으로 2 명이 남는다. f(6) = f(4) + f(2) * f(2) + f(4)

점화식은 f(2n) = f(2n-2)f(0) + f(2n-4)f(2) + f(2n-6)f(4) … + f(2)f(2n-4) + f(0)f(2n-2) 이다.

코드

---

n = int(input())

shakeHands = [1, 1] + [0] * (n // 2 - 1)

for i in range(2, (n >> 1) + 1):
    for j in range(i):
        shakeHands[i] += shakeHands[j] * shakeHands[i-1-j]
        shakeHands[i] %= 987654321

print(shakeHands[n >> 1])