BOJ 26524 - 방향 정하기 (Python3)

이번 주는 각종 대회들로 가득 찬 한 주였다. 목요일에는 Zero One 오픈 콘테스트, 금요일에는 GBS 오픈 콘테스트, 토요일에는 제1회 미적확통컵까지...

가장 높은 점수를 챙긴 것이 제1회 미적확통컵이었다. 그 중에서 조금 풀이과정이 기발하고 과정이 비자명한 문제를 가지고 왔다.

H번 문제, 방향 정하기이다.

 

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

---

문제

n개의 점이 있다. 어떤 두 점을 잡더라도 항상 하나의 간선으로 이어져 있도록 간선이 총 \(\frac{n(n-1)}{2}\)개 있다.

조건을 만족하도록 모든 간선들에 방향을 정해주는 방법의 수를 구하자.

조건: 각 점에서 출발해서 간선 방향을 따라 어떻게 이동해도 출발한 점으로 돌아올 수 없다.

 

입력

첫 번째 줄에 n이 주어진다. (2 ≤ n ≤ 1000000)

 

예제 입력)

2

 

출력

조건을 만족하는 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.

 

예제 출력)

2

 

---

내 코드

n,ans,p = int(input()),1,10**9+7
for i in range(1,1+n): ans = (ans*i)%p
print(ans)

 

직관적으로 생각해 보자. 어떤 점에서 출발해도 돌아올 수 없는 방법은 어떤 방법이 있는가?

점들을 일렬로 세운 다음 왼쪽에서 오른쪽으로 가는 방향으로 화살표를 찍어 주면 된다. 일렬로 세우는 경우의 수가 n!가지이므로, 답은 n!를 p로 나눈 경우의 수다.

물론 미리 n!를 계산하고 p로 나눈다면 메모리와 시간 양 쪽 모두 터져나갈 테니 반복문을 통해서 한 번 곱할 때마다 p로 나누어 주면  그 염려를 덜 수 있다.

그러나 이걸 가지고 해설이라고 하기는 조금 그렇지 않나? 내가 찍어서 맞힌 방법이 곧 해설이요, 라는 것도 아니고 말이다.

엄밀한 증명을 해 보도록 하자.

 

A→B를 A＜B로 볼 근거는 충분하다. 왜냐? A→B, B→C라면 반드시 A→C이기 때문이다.

그렇지 않다면 A에서 출발해 B와 C를 순서대로 경유한 다음 A로 들어오는 순환 경로가 존재하고, 이게 전제에 모순이 되어 버린다.

이를 만족시키는 관계를 추이적 관계라고 부른다. 또한 같은 점 간의 관계도 부설해서, A→A라고 정의하게 된다면 일단 →는 반사 관계이다.

또한 A→B이고 동시에 B→A라면 A=B라는 반대칭 관계 역시 마땅히 성립한다. 왜? 모든 간선에 방향이 성립되어 있으므로, 같은 길을 양 방향으로 오고 갈 수가 없기 때문이다.

수학에서 이 세 관계를 모두 만족시키는 특별한 관계를 무엇이라고 부르는지 아는가? 그렇다. 순서 관계이다, ≤와 같은!

 

이제 →를 모조리 ≤으로 치환할 수 있다. 방금 →이 순서관계임을 보였기 때문에.

또한, 어떠한 두 점 A, B를 가지고 와도 A가 더 작거나(A→B) B가 더 작거나(A→B)를 만족시키기 때문에, 그래프의 정점 간에 화살표로 관계 매긴 집합인 (V, →)=(V, ≤)은 유한 전순서 집합이다.

유한 전순서 집합은 항상 정렬 집합임은 집합론적으로 증명이 가능하다. 여기서 정렬집합이란 임의의 부분집합에 대해서 최소 원소가 존재하는 집합이다.

 

그러면 V의 최소 원소를 고르는 가짓수는 n가지이다. 이걸 A라고 두면, V-{A}의 최소 원소를 고르는 가짓수는? n-1가지이다.

다시 이걸 B라고 두면, V-{A,B}의 최소 원소를 고르는 가짓수는? n-2가지이다. 이렇게 계속 곱해 나가면, V에 순서를 주는 경우의 수 n!을 얻게 되는 것이다.

 

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

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