블로그 옮겼습니다

ECPC 2016 G. The Galactic Olympics 본문

Algorithm/Problem Solving

ECPC 2016 G. The Galactic Olympics

sgc109 2017. 9. 6. 14:37

문제 링크


\(0\lt{N}\le{10^3}\)

\(0\lt{K}\le{10^6}\)

문제는 간단하다. N개의 사람이 있고 K개의 경기가 있다.

모든 경기는 적어도 한명은 참가되어야하지만 딱 한사람만 참가할 수 있다.

각 사람은 적어도 한 경기는 해야하고 한 사람은 여러개의 경기를 할 수가 있다.

이 때 경기가 배정되는 경우의 수를 구하는 문제이다.


우선 K가 10^6인건 훼이크라는 것을 알 수가 있다. 왜냐하면 K가 N보다 크면 모든 사람에게 적어도

한경기씩 배정할 수가 없기 때문이다. 그렇기 때문에 K > N 이면 바로 0 을 출력하고 넘어간다면

K <= N 이라는 것이 보장이 된다. 그러고나서

처음에 한명씩 차례로 보면서 경기를 선택하는 모든 경우의수를 계산하는 방식으로 생각을 했다. 즉,

dp[i][j] : i번째 사람까지 j번째 경기 까지가 배정되는 경우의 수

로 두고, i번째 사람이 1경기를 하는경우, 2경기를 하는경우, ...., j - i + 1경기를 하는 경우를 모두 더해주는 식으로

하여 점화식이 아래와 같이 나왔다.

\(dp[i][j] = \sum_{k=1}^{j-i+1}{dp[i-1][j-k]} \cdot _{N-j+k}C_{k}\)

하지만 이 점화식으로 문제를 풀려면 O(N^3) 이 걸린다. 너무 느리기 때문에

특정 식을 유지하면서 O(N^2) 에 풀 수 없을까 고민도해보고 점화식도 약간 포괄적으로 바꿔보려고 해봤지만

불가능해 보였다. 


각각의 사람에게 경기를 배정한다고 생각하지말고 반대로 각각의 경기를 사람들에게 배정한다고 생각해보자.

그리고 앞에서는 사람과 경기에 순서를 정해놓고 하나씩 배정하고 지나갔지만 이번에는 경기는 순서를 정하지만

사람은 불특정 i명으로 생각해보자. 그럼 부분문제를 이렇게 정의할 수 있다.

dp[i][j] : 총 K명의 사람중에 불특정 i명의 사람에게 j번째 경기까지를 배정하는 경우의 수

여기서 조금 헷갈릴 수 있는 부분이 K가 달라지만 점화식이 달라진다는 것이다. 왜냐하면 K의 값이 달라짐에 따라

i명의 사람에게 j번째 경기까지를 배정했을 때 아직 한 경기도 배정받지 못한 사람이 존재할 수도 있고

존재하지 않을 수도 있기 때문이다. 그렇기 때문에 다른 케이스에 대해 부분문제 테이블을 채워 넣으려면

아예 처음부터 다시그려야 한다. 아무튼 부분 문제를 위와 같이 정의하면 각각의 경기마다 간단한 두가지 케이스로

나눌 수가 있게 된다. 

1. 이미 1경기 이상을 배정받은, 즉 i명 안에 포함되는 누군가에게 j번째 경기를 할당하는 경우.

2. 아직 1경기도 배정받지 못한, 즉 K - i 명안에 포함되는 누군가에게 j번째 경기를 할당하는 경우.

만약 1번 경우라면 1경기라도 배정받은 사람의 수는 그대로이기 때문에 i는 그대로, 그리고 i명 중에

누구에게도 배정할 수 있기 때문제 i가지의 경우의 수가 있으므로 dp[i][j + 1] * i 에 더해지며

2번의 경우라면 1경기이상 배정받은 사람의 수가 1증가하면서 K - i 명 중 누구에게라도 경기를 배정할 수

있기 때문에 dp[i + 1][j + 1] * (K - i) 에 더해진다. 반대 방향으로 생각하면, j번째 경기가

원래 1경기도 배정받지 못한 사람에게 배정되었는지, 원래 1경기 이상 배정 받은 사람에게 배정해 주었는지에 따라

\(dp[i][j] = dp[i][j - 1] \cdot i + dp[i - 1][j - 1] \cdot (K - i + 1)\)

이라는 점화식으로 바꿀 수가 있다.

이 풀이에서 중요한 것은 사람은 특정하지 않으면서 경기는 순서를 강제하는 것이다.

우선 경기의 순서를 강제함으로써 중복을 막았다. 왜냐하면 한번 경기를 누구에게 할당할지를 정하고 지나가버리면

그 경기는 다시 보지 않기 때문에 현재 경기를 누구한테 할당하느냐에 따라 그 다음 경기들을 어떻게 할당하던

모두 다른 방법이 되어버리기 때문이다. 그 다음으로 사람을 특정하지 않음으로써

부분 문제를 포괄적으로 바꾸고 특정 수를 곱하는 것으로 복잡도를 한차원 줄였다.

부분 문제를 정의하기에 따라 각각의 사람이 구분될 필요가 사라진 것이다. 현재 경기를 누구에게 배정하던간에

중요한 것은 단지 현재 몇명의 사람이 현재 경기를 1개이상 배정받았는지. 이것 하나이기 때문이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
 
int T, K, N;
ll dp[1003][1003];
int main() {
    fastio();
    freopen("galactic.in""r", stdin);
    cin >> T;
    while(T--){
        memset(dp,0,sizeof(dp));
        dp[0][0= 1;
        cin >> N >> K;
        if(K > N){
            cout << 0 << '\n';
            continue;
        }
        for(int i = 1; i <= K; i++){
            for(int j = 1; j <= N; j++){
                dp[i][j] = (dp[i][j - 1* i + dp[i - 1][j - 1* (K - i + 1)) % mod;
            }
        }
        cout << dp[K][N] << '\n';
    }
    return 0;
}
cs


'Algorithm > Problem Solving' 카테고리의 다른 글

2017 SCPC 예선 2차 Divisor  (3) 2017.09.10
Codeforces Round #299 (Div. 2) D. Tavas and Malekas  (0) 2017.09.08
BOJ 1153번 네개의 소수  (0) 2017.08.23
BOJ 2104번 부분배열 고르기  (0) 2017.08.23
BOJ 8217번 유성  (0) 2017.08.21
Comments