BOJ 백준 19645번 햄최몇?

 

BOJ 백준 19645 햄최몇?

 

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

19645번: 햄최몇?

 

N개의 햄버거가 있고, 각 햄버거마다 먹을 때 얻을 수 있는 효용 값이 정해져 있다. 또한 섭취한 햄버거의 효용 값은 누적된다. 두 명의 선배와 막내 길원이가 모여서 N개의 햄버거를 먹을 때, 선배가 더 많은 효용을 얻게 하면서 막내가 얻을 수 있는 효용의 최댓값을 구하는 것이 문제이다.

 

처음에는 Dynamic Programming 풀이법으로 접근하여 다음과 같이 메모이제이션 할 배열을 정의했다.

 

 

dp[i][x][y]: i번째 햄버거까지 봤고, 첫 번째 선배가 얻은 효용이 x, 두 번째 선배가 얻은 효용이 y일 때, 막내가 얻을 수 있는 효용의 최댓값

 

그런데 생각해보면 사실 x 값과 y 값이 결정되면 막내가 얻는 효용 값은 자동적으로 정해진다. 전체 햄버거의 효용 값의 합에서 x와 y 값을 빼면 그게 바로 막내가 얻는 효용 값이다. 따라서 다른 방식의 접근이 필요해보였다.

 

 

dp[i][x][y]: i번째 햄버거까지 봤을 때, 첫 번째 선배가 얻은 효용이 x, 두 번째 선배가 얻은 효용이 y인 경우가 가능한지의 여부

 

하지만 위의 배열을 정의하면 메모리 제한 초과가 발생한다. 각 선배가 얻을 수 있는 효용의 최댓값이 2500이므로 50 * 2500^2는 문제에서 주어진 메모리 제한을 넘는다. (사실 1024MB여서 메모리 초과가 나오진 않는다.)

 

좀 더 나아가서 과연 i번째 햄버거까지 봤다는 정보가 필요한지 의문이 들었다. 사실 어떠한 햄버거를 이제까지 먹어서 첫 번째와 두 번째 선배가 누적한 효용값이 x, y가 되는 게 가능한지가 중요한 게 아니라, 그러한 경우가 가능한지 그 자체가 관건이다. 따라서 i번째 햄버거에 관한 정보는 기억할 필요가 없고, 다음과 같이 배열의 정의를 수정했다.

 

 

dp[x][y]: 첫 번째 선배가 얻은 효용이 x, 두 번째 선배가 얻은 효용이 y인 경우가 가능한지의 여부

 

첫 번째부터 N번째 햄버거까지 차례대로 탐색한다. i - 1번째 햄버거까지 살핀 이전 상태에서 선배 둘 중 한 사람이 i번째 햄버거를 먹었을 때, 선배들의 효용 누적 값이 각각 x, y가 될 수 있는지를 구한다. 이를 간단히 정리하면 다음과 같다.

 

 

 

a[i]: i번째 햄버거를 먹을 때 얻게 되는 효용

sum: 모든 햄버거 효용 값의 합

dp[x][y] |= (dp[x - a[i]][y] || dp[x][y - a[i]])

 

 

 

주의할 점은 이를 구하는 과정에서 선배의 효용값이 커야한다는 조건을 판단하지 않아야 한다. 미리 모든 경우의 수에 관해 가능한지를 구해놓고, 최종적으로 나중에 선배의 효용값이 큰 경우 중에서 막내가 얻는 효용의 최댓값을 따로 알아보면 된다. 이유를 단순하게 설명하자면, i번째 햄버거까지 탐색한 상태에서는 막내의 효용값이 선배들보다 크다 하더라도 i + 1번째 햄버거부터 선배들이 나머지 대부분을 먹게 했을 때 결과적으로 선배의 효용값이 막내보다 크게 될 가능성이 있어서다.

 

문제를 풀고 나서 검색해보니 이러한 풀이를 Knapsack 문제 풀이법의 일종으로 보는 것 같다. 사실 Knapsack 문제가 Dynamic Programming 알고리즘으로 해결 가능한 문제이니까 어찌 보면 당연한 말인 듯 싶다.

 

 

#include <cstdio>
#include <algorithm>
using namespace std;


const int N_MAX = 50;
const int T_MAX = 2500;


int n;
int a[N_MAX + 1];
bool dp[T_MAX + 1][T_MAX + 1];


int main(){
    int sum = 0;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    dp[0][0] = true;
    
    for (int i = 1; i <= n; i++){
        for (int j = sum; j >= 0; j--){
            for (int k = sum; k >= 0; k--){
                if (j - a[i] >= 0) {
                    dp[j][k] |= dp[j - a[i]][k];
                }
                if (k - a[i] >= 0){
                    dp[j][k] |= dp[j][k - a[i]];
                }
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= sum; i++){
        for (int j = 0; j <= i; j++){
            if (dp[i][j] && j >= (sum - i - j)){
                ans = max(ans, sum - i - j);
            }
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}