BOJ 26524 : 방향 정하기

• 문제 링크 : boj.kr/26524
• 난이도 : G5
• 태그 : 그래프, 조합론

26524번: 방향 정하기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    ll ans = 1;
    for(ll i = 1; i <= n; i++) {
        ans *= i;
        ans %= 1000000007ll;
    }
    cout << ans;

    return 0;
}

---

풀이

어떤 한 점 $A_i$에 대해서 나가는 방향의 간선과 연결된 점의 집합을 $O_i$, 들어오는 방향의 간선과 연결된 점의 집합을 $I_i$라고 하자.

 

$|O_i|=N$인 어떤 i는 반드시 하나가 존재한다. 만약 이런 점이 존재하지 않는다고 해보자.

그렇다면 임의의 점 k에 대해 $|O_k|$는 $N-1$이하이고, $|I_k|$는 1이상일 것이다. 이때 $O_k$의 어떤 점에서 $I_k$의 어떤 점으로 향하는 간선이 없어야 한다. 따라서 $I_k$의 모든 점 x에 대해 $|O_x| \ge |O_k| + 1$이다. 반복해보면 $|O_i|=N$인 어떤 i는 반드시 하나가 존재함을 보일 수 있다.

 

$|O_i|=N$인 어떤 점 $A_i$는 다른 N-1개의 점에 대해 독립적이다. 따라서 남은 N-1개의 점을 분석하기 위해 앞의 방법을 똑같이 이용할 수 있다. 반복하면 각각의 점에 대해 나가는 방향의 간선이 $N, N-1, N-2, \cdots, 1$임을 알 수 있다.

 

이제 어떤 점이 몇 개의 나가는 방향의 간선을 가질지 매칭하는 문제로 바뀌게 되고, 이는 N!임을 알 수 있다.