19645: 햄최몇?

19645번: 햄최몇?

문제

세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다.

막내 길원이는 문득 중요한 사실을 깨달았다. 바로, 개수가 중요한 것이 아니라 최대 효용이 중요하다는 것이었다! 이들은 바로 N개의 햄버거를 준비했다. 그리고 이 햄버거를 사이좋게 나누어 먹었다. 각 모질이들이 얻을 수 있는 효용은 이들이 먹은 햄버거들의 효용의 합이다. 또한 나름의 서열과 규칙이 있어, 존경하는 선배님들보다는 높은 효용을 누려서는 안 된다.

막내 길원이는 선배님들을 존경하기 때문에 규칙을 따라야 하는 한편, 햄버거를 잘 분배하여 본인이 얻을 수 있는 효용이 최대가 되도록 하고 싶다.

예제

입력	결과
10 4 37 50 2 6 15 2 13 3 10	46

---

문제 요약

N개의 햄버거 → 3명이 나눠먹는다.

각자 얻는 효용 = 먹은 햄버거 효용의 합

후배는 선배보다 높은 효용 X

결과: 막내의 효용의 합의 최대값

일단 풀어본 방법

• 막내가 얻는 효용: 전체 햄버거 효용 합 - 선배 1이 얻은 효용 - 선배 2가 얻은 효용
• dp (boolean): 선배1이 x효용일 때 선배2가 y효용을 얻는 것이 가능한 지 여부
  • dp 배열을 채울 때는 막내의 효용은 고려하지 않는다.
  • dp[x][y] = (dp[x][y] || dp[x - ham[i]][y]) : x, y 효용이 가능하거나 x-(현재 햄버거 효용), y효용이 가능하면 x,y 효용이 가능하다.
    1. 현재 탐색 중인 햄버거를 선배 1이 먹는 경우
    2. 현재 탐색 중인 햄버거를 선배 1이 먹지 않는 경우
  • 선배 2의 경우도 동일한 방식으로 dp[x][y] = (dp[x][y] || dp[x][y - ham[i]])

boolean[][] dp = new boolean[sum+1][sum+1];
dp[0][0] = true; // 0 >= 0 이므로 가능한 조합
for(int i=1; i<n+1; i++){
    for(int x=sum; x>=0; x--){
       for(int y=sum; y>=0; y--){
            if(x - ham[i] >= 0)
                dp[x][y] |= dp[x - ham[i]][y];
            if(y - ham[i] >= 0)
                dp[x][y] |= dp[x][y - ham[i]];
        }
    }
}​

• 가능한 선배1, 2 효용 조합 중 막내가 갖게 될 효용이 최대가 되는 값을 찾는다.
  • 즉, sum - 선배1 효용 - 선배2 효용의 max값
  • 단, 선배2 효용 > 막내 효용을 지켜야 한다.

for(int i=0; i<sum+1; i++){ // i: 첫째 효용
    for(int j=0; j <= i; j++){ // j: 둘째 효용 <= 첫째 효용
        int last = sum - i - j; // last: 막내 효용
        if(dp[i][j] && (j >= last)){ // 가능한 효용 조합 && 둘째 효용 > 막내 효용
            answer = Math.max(answer, last);
        }
    }
}​

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P19645 { // 햄최몇?
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] ham = new int[n+1]; // 햄버거 효용
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<n+1; i++){
            ham[i] = Integer.parseInt(st.nextToken());
            sum += ham[i];
        }

        boolean[][] dp = new boolean[sum+1][sum+1]; // dp[x][y]: 선배1 x효용일때 선배2가 y효용을 얻는 것이 가능한가?
        // dp[x][y] = 햄버거 전체 효용 - x -y
        dp[0][0] = true; // 0 >= 0
        for(int i=1; i<n+1; i++){
            for(int x=sum; x>=0; x--){
                for(int y=sum; y>=0; y--){
                    if(x - ham[i] >= 0)
                        dp[x][y] |= dp[x - ham[i]][y];
                    if(y - ham[i] >= 0)
                        dp[x][y] |= dp[x][y - ham[i]];
                }
            }
        }

        int answer = 0;
        for(int i=0; i<sum+1; i++){ // i: 첫째 효용
            for(int j=0; j <= i; j++){ // j: 둘째 효용 <= 첫째 효용
                int last = sum - i - j; // 막내 효용
                if(dp[i][j] && (j >= last)){ // 가능한 효용 && 둘째 > 막내
                    answer = Math.max(answer, last);
                }
            }
        }

        System.out.println(answer);
    }

}

---

남은 고민점

• dp 배열을 꼭 boolean으로 구현해야 하는가?
• dp 배열 자체에 선배1이 x효용, 선배2가 y효용일 때의 막내의 효용을 저장하는 방법으로는 풀 수 없을까?