[Python] 1670번 정상 회담 2 / 17268번 미팅의 저주

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

1670번: 정상 회담 2

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

17268번: 미팅의 저주

---

 

23/12/06

 

 

카탈란 수 문제다. 두 문제는 완전히 동일한 문제이기 때문에 같이 올린다.

---

 

문제 접근 방식:

 

 

예제 출력 보고 카탈란 수 임을 인지한 뒤, 카탈란 수를 출력하는 코드를 작성하면 맞았습니다를 받을 수 있다.

 

이 문제에서 점화식이 카탈란 수로 나오는 이유는 다음과 같다.

 

먼저 $N$명의 사람이 악수하는 경우를 생각해보자.

 

그러면 우리는 악수하는 사람과 악수하는 사람끼리는 서로 교차하면 안 된다는 조건을 통해, 두 사람이 악수한다면, 왼쪽과 오른쪽으로 구역이 분할됨을 확인할 수 있다.

 

따라서, $N$명의 사람이 악수하는 경우의 수를 $C_N$이라고 하고, 첫 번째 사람이 $i$번째 사람과 악수를 했다면, 우리는 두 번째 사람부터 $i-1$번째 사람 그룹과 $i+1$번째 사람부터 $N$번째 사람끼리의 그룹은 서로 악수를 할 수 없다는 사실을 알고 있다.

 

즉, 이때의 경우의 수는 $C_{i-2} * C_{N-i}$라는 사실을 확인할 수 있고, 첫 번째 사람은 $2$번째 사람부터 $N$번째 사람까지 모두 악수할 수 있으므로, 이를 모두 합한 값은 카탈란 수의 점화식이 됨을 확인할 수 있다.

 

따라서, 이를 그대로 구현해 주면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 1670번 정상 회담 2
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
import sys
input = sys.stdin.readline

MOD = 987_654_321
Catalan = [0 for _ in range(5002)]
Catalan[0], Catalan[1] = 1, 1
for i in range(2, 5002):
    C = 0
    for j in range(i):
        C += (Catalan[j]*Catalan[i-j-1])%MOD
    C %= MOD
    Catalan[i] = C
N = int(input())
print(Catalan[N//2])