햄최몇?( BOJ 19645 )

문제 : https://www.acmicpc.net/problem/19645

19645번: 햄최몇?

 

문제 파악하기

3명의 사람이 N개의 햄버거를 나누어먹을 때, 가장 적은 효용을 얻게 되는 사람의 최댓값을 구하는 문제입니다. 효용은 햄버거를 먹으면 얻게 되며, 햄버거는 한 사람이 무조건 다 먹어야 하기 때문에 단순히 3등분 하는 방법으로는 구할 수 없습니다. 따라서, 이 경우에는 효율적으로 가능한 경우를 탐색해야 합니다. 가장 단순하게 재귀 함수를 사용하는 방법부터 배열을 사용하는 방법까지 순서대로 하나씩 확인해보겠습니다.

 

문제 해결하기 

우선, 가장 간단한 방법을 떠올려보겠습니다. 3명의 사람 중 한 명은 무조건 햄버거를 먹어야 합니다. 따라서, 우리는 현재 햄버거의 번호와 3명의 사람이 얻은 효용을 매개변수로 하는 재귀함수를 구현할 수 있습니다.

 

sv( idx, A, B, C ) // idx번째 햄버거를 먹을 때의 { A, B, C }의 효용을 가진 상태

 

다만, 이 재귀함수는 시간 복잡도가 O(3ⁿ)이기 때문에 N이 최대 50인 이 문제를 해결하기에는 부족합니다. 또한 메모이제이션을 사용하기에는 [ 50*2500*2500*2500 =  대략 7000억 ] 크기의 배열이 필요하기에 불가능합니다. 그렇다면 어떻게 최적화를 시킬 수 있을까요? 생각해보면 3명의 효용을 꼭 적어야할 필요는 없습니다. 2명의 효용만으로도 나머지 한 명의 효용을 쉽게 구할 수 있습니다. 따라서,  재귀함수의 매개변수를 4개에서 3개로 줄일 수 있습니다.

 

sv( idx, A, B ) // idx번째 햄버거를 먹을 때, { A, B, sum-(A+B) }의 효용을 가진 상태

 

이렇게 3개의 매개변수가 되면 필요한 배열의 크기가 줄어 필요한 배열의 크기도 줄어듭니다. 하지만 아직도 [ 50*2500*2500 = 대략 3억 ]의 크기가 필요합니다. 또한, 시간 복잡도는 내부 알고리즘을 고치지 않았기에 여전히 느리기에 메모이제이션을 사용하지 않을 수는 없습니다. 그렇다면 여기서 어떻게 더 줄일 수 있을까요?

 

우리는 이 시점에서 매개변수 중 idx 값의 필요성을 다시 한 번 생각해볼 수 있습니다. 우리가 idx 값을 사용하는 건 각각의 햄버거를 먹었을 때의 다음 상태를 확인하기 위해 사용합니다. 즉, 탐색에서 사용하는 이전 상태 값은 (idx-1) 값만 사용하기에 모든 idx 값마다 배열을 만들 필요는 없습니다. 따라서, 재귀 함수를 반복문으로 바꾼다면 3차원 배열이 아닌 2차원 배열을 사용하여 점화식을 설계할 수 있습니다.

 

dp[A][B] // { A, B, sum-(A+B) } 효용을 가질 수 있는지 여부

 

점화식을 활용하여 배열을 2차원으로 설계한 다음, 햄버거의 개수만큼 반복문을 돌리면서 다음 상태를 확인하면 나올 수 있는 모든 효용의 경우를 구할 수 있습니다. 시간 복잡도 역시 2차원 배열만큼 줄었기에 충분히 시간 내에 확인 가능합니다. 모든 경우의 수를 구한 다음에는 반복문을 통해 dp[A][B]가 1인 값들만 탐색하여 { A, B, sum-(A+B) } 의 값 중 최솟값을 구하고, 그 중에서 최댓값을 구하면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#import <algorithm>
#define NMAX 55
#define VMAX 2505
using namespace std;
 
int N, sum;
int inp[NMAX];
 
int tmp, tot, ret;
int dp[VMAX][VMAX];
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i]);
        sum += inp[i];
    }
    
    dp[0][0] = 1;
    for(int idx=1;idx<=N;idx++) {
        tot += inp[idx];
        
        // 현재 햄버거로 만들 수 있는 경우의 수 탐색
        for(int i=tot;i>=0;i--) {
            for(int j=tot;j>=0;j--) {
                if(dp[i][j]) {
                    dp[i+inp[idx]][j] = 1;
                    dp[i][j+inp[idx]] = 1;
                }
            }
        }
    }
    
    // 모든 경우의 수 탐색
    for(int i=0;i<=sum;i++) {
        for(int j=0;j<=sum;j++) {
            if(!dp[i][j]) continue;
            
            tmp = min( sum-(i+j), min( i, j ) );
            ret = max( ret, tmp );
        }
    }
    
    // 출력
    printf("%d", ret);
}
 

후기

점화식을 어떻게 구현할 지 고민이 많았던 문제입니다. 배낭 채우기 문제 유형은 항상 배열을 어떻게 효율적으로 설계할 수 있는지에 난이도가 결정된다는 걸 다시 느낄 수 있는 문제였습니다. 동적 프로그래밍을 연습하는 사람에게 추천하고 싶은 문제입니다.