[COCI] 백준 10740 - ACM

www.acmicpc.net/problem/10740

문제 소개

Zagreb 대학교에 속한 스테판, 이반, 구스타프가 모로코에서 열리는 ICPC WF를 참석한다.

 

그들의 전략 가이드 고란은 필승전략을 가져왔는데 그 전략은 다음과 같다.

 

대회 극초반에 각 멤버가 n문제의 난이도를 분석한다. (1부터 5까지 있으며 5가 제일 어렵다.)

 

그리고 각 팀원이 풀 문제를 연속적으로 분배한다. (1 2 3 4 5 번이 있으면 1 2 / 3 / 4 5 처럼 분배할 수 있다.)

 

어떤 사람이라도 문제를 풀지 않는 경우는 없어야 한다.

 

이렇게 문제를 분배할 때 각 팀원이 담당한 문제의 분석 난이도 합이 최소가 되는 분배 방법을 찾아야 한다.

풀이 - 탑 다운 dp

다음 이차원 dp 테이블을 생각해보자.

 

dp[i][j] := i번째 문제를 j번째 팀원이 풀 때 최소 합

 

이렇게 하면 각 단계에서 j가 문제 풀이를 계속하느냐, 다음 사람에게 문제 풀이를 맡길 것이냐 두 갈래로 결정할 수 있다.

 

다만, 바텀 업 dp로 해결을 시도할 경우 구한 결과에서 세 사람이 모두 최소 한 문제 이상을 풀었다는 보장이 없다.

 

탑 다운 dp를 통해 재귀함수에서 현재 인덱스에서 누가 풀었는지를 인자로 전달해주면 이를 쉽게 판별할 수 있다.

 

또한 문제 푸는 순서는 고정되어있지 않으므로 세 사람을 나열하는 6가지 경우에 대해 모두 계산하면서 답을 비교해야 한다.

 

게시글의 구현에서는 세 사람을 나열하는 경우를 모두 이차원 배열로 저장해놓고 계산할 때 인덱싱을 하여 값을 더했다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[150000][3];
int team[150000][3];
int permu[6][3] { {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };
int n;
int res = 1e9;
 
int memo(int idx, int curperm, int permidx);
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; ++i)
        cin >> team[i][0];
    for (int j = 0; j < n; ++j)
        cin >> team[j][1]; 
    for (int k = 0; k < n; ++k)
        cin >> team[k][2];
    
    for (int i = 0; i < 6; ++i)
    {
        memset(dp, -1, sizeof dp);
        res = min(res, memo(0, i, 0));
    }
        
    cout << res;
}
 
int memo(int idx, int curperm, int permidx)
{
    int &ret = dp[idx][permu[curperm][permidx]];
 
    if (ret != -1)
        return ret;
    
    if (idx == n - 1)
    {
        if (permidx != 2)
            return 1e9;
        else
            ret = 0;
    }
    
    ret = team[idx][permu[curperm][permidx]];
 
    int tmp = 0;
 
    if (idx < n - 1)
    {
        tmp = memo(idx + 1, curperm, permidx);
        if (permidx != 2)
            tmp = min(tmp, memo(idx + 1, curperm, permidx + 1));
    }
    
    return ret += tmp;
}

바텀 업 dp로 풀기 위한 방법을 생각하느라 많은 시간을 썼다.