[USACO] 백준 14165 - Team Building

www.acmicpc.net/problem/14165

문제 소개

농부 존과 폴은 스테이트 페어에서 best in show라는 경쟁을 한다.

 

서로 가지고 있는 소들에게 점수를 부여하고 각 농부가 K마리의 소를 서로 점수가 높은 순으로 매칭하는데 한 진영의 소가 다른 진영의 소보다 모두 높은 점수로 매칭되면 이긴다.

 

K가 주어지고 농부 존과 폴이 각각 N, M마리의 소를 가지고 있을 때 존이 이기는 경우의 수를 $10^9 + 9$로 나눈 모듈러를 출력해야 한다.

풀이

단순하게 존이 i번째 소, 폴이 j번째 소까지 각각 k마리를 뽑아서 존이 이기는 경우를 삼차원 동적계획법으로 풀 수 있다. (dp[i][j][k])

 

다만 서로의 소를 매칭하는 경우를 일일이 탐색하면 시간복잡도는 $O(NM \times NMK)$가 되고 시간 내에 풀 수 없다.

 

이를 빠르게 풀기 위해 재미있는 방법이 사용된다.

 

k - 1마리를 뽑았을 때의 dp 테이블을 저장하여 이를 k마리 뽑았을 때 테이블에 반영하는 것이다.

 

이렇게 하면 dp 테이블은 다음과 같이 변화한다.

 

소를 1마리 뽑을 때 존이 이기는 경우를 담은 dp 테이블 -> 소를 2마리 뽑을 때 존이 이기는 경우를 담은 dp 테이블 -> ... -> 소를 K마리 뽑을 때 존이 이기는 경우를 담은 dp 테이블

 

이렇게 K마리 뽑는 경우까지 테이블을 갱신해나가게 되면 테이블은 이차원으로도 충분하며 k - 1마리의 소를 매칭했을 때의 최적해를 알고 있으므로 매칭하는 경우를 탐색할 필요 없이 $O(NMK)$의 시간복잡도로 풀 수 있게 된다.

구현

dp 테이블의 계산은 3중 반복문을 통해 이루어진다.

 

K번 반복을 돌면서 그 안에 2중 반복문이 두개가 있는데 각 파트마다 처리하는 부분은 이렇다.

 

1. k - 1마리 뽑았을 때의 테이블을 k마리 뽑았을 때의 테이블에 반영하는 과정

memset(tmp, 0, sizeof tmp);
for (int a = 1; a <= n; ++a)
    for (int b = 1; b <= m; ++b)
        if (fj[a] > fp[b])
            tmp[a][b] = dp[a - 1][b - 1];
        
copy(&tmp[0][0], &tmp[0][0] + 1001 * 1001, &dp[0][0]);

tmp는 임시 테이블이고 여기서 존의 a - 1번째 소, 폴의 b - 1번째 소까지 각각 k - 1마리의 소를 뽑았을 때 계산된 dp 테이블이 있다.

 

만약 존의 a번째 소의 점수 > 폴의 b번째 소의 점수이면 k마리의 소를 뽑았을 때로 테이블을 확장할 수 있으며 경우의 수는 변하지 않으므로 tmp[a][b] = dp[a - 1][b - 1]이 된다.

 

그리고 k마리 소를 뽑았을 때 경우의 수 계산을 위해 이 임시 테이블의 값을 dp테이블로 옮겨준다.

 

2. 반영된 테이블을 계산하는 과정

for (int a = 0; a < n; ++a)
{
    for (int b = 0; b < m; ++b)
    {
        dp[a + 1][b + 1] += dp[a][b + 1];
        dp[a + 1][b + 1] += dp[a + 1][b];
        dp[a + 1][b + 1] -= dp[a][b];
        dp[a + 1][b + 1] %= mod;
    }
}

반영된 테이블을 가지고 경우의 수를 계산한다.

 

dp[a + 1][b + 1]에 dp[a][b + 1]과 dp[a + 1][b]를 더해주면 dp[a][b]가 중복되므로 이를 한번 빼준다.

 

이렇게 K번 반복한 다음 dp[N][M]의 값이 답이 된다.

 

전체 코드

#include <bits/stdc++.h>
 
#define mod 1000000009;
 
using namespace std;
using ll = long long;
 
int n, m, k;
 
int fj[1001], fp[1001];
ll dp[1001][1001];
ll tmp[1001][1001];
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; ++i)
        cin >> fj[i];
 
    for (int j = 1; j <= m; ++j)
        cin >> fp[j];
    
    sort(fj + 1, fj + n + 1);
    sort(fp + 1, fp + m + 1);
    
    fill(&dp[0][0], &dp[0][0] + 1001 * 1001, 1);
    
    for (int i = 0; i < k; ++i)
    {
        memset(tmp, 0, sizeof tmp);
        for (int a = 1; a <= n; ++a)
            for (int b = 1; b <= m; ++b)
                if (fj[a] > fp[b])
                    tmp[a][b] = dp[a - 1][b - 1];
        
        copy(&tmp[0][0], &tmp[0][0] + 1001 * 1001, &dp[0][0]);
        
        for (int a = 0; a < n; ++a)
        {
            for (int b = 0; b < m; ++b)
            {
                dp[a + 1][b + 1] += dp[a][b + 1];
                dp[a + 1][b + 1] += dp[a + 1][b];
                dp[a + 1][b + 1] -= dp[a][b];
                dp[a + 1][b + 1] %= mod;
            }
        }
    }
    
    while (dp[n][m] < 0)
        dp[n][m] += mod;
    cout << dp[n][m];
}