[BOJ 2682] 최대 사이클 1

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

2682번: 최대 사이클 1

---

Tag : Combinatorics

 

풀이

순열 \(P\)는 \( 1<=i<=N \) 한 모든 i를 포함한다. 이 때 1에서 시작해 \( P_{1} \) -> \( P_{P_{1}} \)....를 반복해

1로 돌아오는 사이클 안에서 가장 큰 수를 구하는 문제이다. 일단 문제 이름부터 사이클이니 그래프로 해석해봐야 할 듯한 느낌이 강하게 든다. 그러기 위해서 일단 \(1<=i<=N\)인 i\)를 정점으로 보고 \(i\)와 \(P_{i}\)는 공역과 치역의 관계이니 \(P_{i}\)를 \(i->P_{i}\)인 간선으로 생각해보자. 여기서 조금 생각해보면 발견할 수 있는 것이 있다.

 

"위 정의의 그래프를 SCC들로 분해했을 때 서로 다른 SCC사이에는 간선이 존재하지 않는다"

이게 어딘가 쓸모있지 않을까 하고 10분정도는 날린 듯한데 별 의미없는 짓이었다. 

 

조건을 만족하는 그래프에는 \(1, K\)를 동시에 포함하는 사이클이 존재해야한다. 또 K보다 큰 원소는 포함할 수 없다.

어떻게 나열할지는 나중에 생각하고 \(1, K\)를 포함하는 사이클의 원소를 골라보자.

사이클의 크기를 \(S\)라 하면 \(\binom{K-2}{S-2}\)의 경우의 수만큼 원소를 고를 수 있다. 또 이를 나열하는 경우의 수는 

원순열이기 때문에 \( (S-1)! \)이다. 

 

이제 나머지는 어떻게 배치하냐. 아무렇게나 배치하면된다. 이건 그래프로 생각하지말고 순열을 나열하는 순서 그대로 생각하면 된다. 그래서 \((N-S)!\)가 나오게 되고 이 과정을 정리하면 다음과 같은 식을 얻을 수 있다.

\( \sum_{S=2}^{K}\binom{K-2}{S-2}*(S-1)!*(N-S)! \) 이제 코딩하면 된다.

 

+ YunGoon님에 의하면 \(20!\)까지는 243경으로 long long의 끝자락에 있지만 \(21!\)은 4800경을 넘어가니 long long을 벗어난다고 한다. \(N, K <= 20\)은 출제자가 노린듯.......어질어질...

 

시간복잡도 : \(O(TC * K)\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define endl '\n'
using namespace std;
using ll = long long;

ll fac[33];
ll nCr(ll N, ll R){
    return fac[N]/(fac[N-R]*fac[R]);
}

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

    fac[0] = 1;
    for(int i = 1; i<=25; i++) fac[i] = i * fac[i-1];
    int tc; cin >> tc;
    while(tc--){
        int N, K; cin >> N >> K;
        ll ans = 0;
        for(ll sz = 2; sz <= K; sz++) ans += nCr(K-2,sz-2) * fac[sz-1] * fac[N-sz];
        if(K == 1) ans = fac[N-1];
        cout << ans << endl;
    }
}