BOJ 1670 - 정상 회담 2 (Python3)

보자마자 풀이가 보이는 경우가 있다. 수학적 배경이 있으면 프로그래밍을 하는 데 하등 불편함이 없다는 말은 사실인 듯 하다.

이게 웰노운이 아니라서 다이나믹 프로그래밍으로 문제를 풀었다는 다른 사람의 기여를 보고 놀랐다.

하기사 다이나믹 프로그래밍이 점화식을 프로그램으로 푸는 제법 수월한 방법이기는 하지만... 여기서는 머리를 좀 써 보자.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다.

각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때 완벽하게 악수했다고 한다.

N이 주어지면 완벽하게 악수하는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.

 

예제 입력)

# 예제 입력 1
4

# 예제 입력 2
2

# 예제 입력 3
8

예제 1번의 경우, 왼쪽 2개만 완벽하게 악수하는 방법이다.

출력

완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다.

 

예제 출력)

# 예제 출력 1
2

# 예제 출력 2
1

# 예제 출력 3
14

 

---

내 코드

from math import comb
n = int(input())//2
print((comb(2*n,n)//(n+1))%987654321)

 

뭐가 이리 간단하냐고? 말하지 않았는가. 수학적 배경이 있어서 보자마자 풀이가 보였다고.

 

우선 0명이 완벽한 악수를 하는 경우는 정확하게 1가지이다. 사람이 없으니 악수가 불가능하기는 하지만 일단 그렇다고 하자.

그러면 2n+2명이 완벽한 악수를 하는 경우의 수를 보자. 특정한 한 사람을 정해서 A라고 이름표를 붙이고, A와 악수를 할 사람을 뽑아서 B라고 이름표를 붙이자.

그러면 선분 AB의 왼쪽에도, 선분 AB의 오른쪽에도 짝수 명의 사람이 있어야 한다.

홀수명의 사람이 AB의 왼쪽에 있으면, 그 중 최소한 한 명은 AB의 오른쪽에 있는 사람과 악수하게 될 테니. 그러면 AB와 교차하지 않겠는가?

그러니 AB의 왼쪽에 있는 사람은 2i명, 오른쪽에 있는 사람은 2(n-i)명이다.

 

자, 2n명이 완벽한 악수를 하는 경우의 수를 C(n)이라는 표기법으로 표현하도록 하자.

다시 2n+2명의 케이스로 돌아와서, AB의 왼쪽에 있는 2i명의 사람들은 그 내부에서 완벽한 악수를 해야 한다. 당연히, 그 내부에서 교차점이 생기면 2n+2명의 악수까지도 완벽함이 깨져버릴 테니 말이다.

AB의 오른쪽에 있는 2(n-i)명의 사람도 마찬가지이다. 

그렇다면 이 케이스에서 경우의 수는? 그렇다. C(i)*C(n-i)이 된다.

 

i는 0부터 n까지 어느 수든 될 수 있으므로, \(C(n+1)=\sum_0^n C(i)\cdot C(n-i)\)가 된다.

어딘가 익숙하지 않는가? 그렇다. 카탈란 수다.

이 포스트에서 이미 다룬 바가 있지만, 카탈란 수의 일반항은 \(C(n)=\frac{1}{n+1}\binom{2n}{n}\)으로 주어지게 된다.

따라서 2n명이 악수하는 경우의 수 C(n)을 일반항 공식으로부터 구하여, 987654321로 나눈 나머지를 쓰면 끝이다!

 

이로서 1670번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.