[Java] 백준 19645. 햄최몇?

📌 문제 링크 - https://www.acmicpc.net/problem/19645

 

 

---

 

 

 

 

 

 

문제

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

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

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

 

 

 

입력

첫 번째 줄에 N (1 ≤ N ≤ 50)이 주어진다. N은 햄버거의 수이다.

두 번째 줄에 N개의 양의 정수 ai (1 ≤ ai ≤ 50)가 공백으로 구분되어 주어진다. 각각의 값은 햄버거의 효용을 의미한다.

 

 

 

출력

세 모질이 중 막내 길원이가 얻을 수 있는 효용의 합의 최댓값을 출력한다.

 

 

 

 

---

 

 

풀이

막내 길원이가 선배들보다는 적게 먹으면서 최대한 많이 얻을 수 있는 효용의 최댓값을 구하는 문제다. 

인원이 3명이므로 선배 두 명이 각각 햄버거를 먹을 수 있는 경우를 모두 구해주고 효용의 총합에서 선배 둘의 효용 값을 빼주면 길원이가 얻을 수 있는 효용 값을 알 수 있다. 가능한 조합을 모두 구해준 후, 가능한 경우를 모두 살펴보며 길원이가 선배들보다 높지 않으면서 얻을 수 있는 최댓값을 구하면 된다.

 

 

---

 

 

코드 1

[DP, 냅색]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/19645
public class Main_19645 {
    static int N; // 햄버거의 수
    static int[] V; // 햄버거의 효용

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        init();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int total = 0; // 효용 총합
        for(int i=0; i<N; i++) {
            V[i] = Integer.parseInt(st.nextToken());
            total += V[i];
        }

        int max = getMax(total); // 막내 길원이가 얻을 수 있는 효용의 합의 최댓값
        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }//main

    private static int getMax(int total) {
        boolean[][] dp = new boolean[total+1][total+1]; // [선배1 효용 합][선배2 효용 합]
        dp[0][0] = true;
        
        for(int i=0; i<N; i++) {
            for(int a=total; a>=0; a--) {
                for(int b=total; b>=0; b--) {
                    if(a - V[i] >= 0) {
                        dp[a][b] |= dp[a- V[i]][b];
                    }
                    if(b - V[i] >= 0) {
                        dp[a][b] |= dp[a][b- V[i]];
                    }
                }
            }
        }

        int max = 0;
        for(int a=0; a<=total; a++) {
            for(int b=0; b<=a; b++) {
                // 선배1이 a 만큼, 선배2가 b 만큼 효용을 얻는 게 가능하고,
                // 길원이가 얻을 수 있는 효용이 그보다 높지 않다면
                if(dp[a][b] && b >= (total - a - b)) {
                    max = Math.max(max, total - a - b); // 최댓값 갱신 
                }
            }
        }

        return max;
    }//getMax

    private static void init() {
        V = new int[N];
    }//init

}//class

 

 

 

코드 2

[재귀, DP]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/19645
public class Main_19645 {
    static int N; // 햄버거의 수
    static int[] V; // 햄버거의 효용
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        init();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int total = 0; // 효용 총합
        for(int i=0; i<N; i++) {
            V[i] = Integer.parseInt(st.nextToken());
            total += V[i];
        }

        dp = new int[total+1][total+1];
        for(int i=0; i<=total; i++) {
            Arrays.fill(dp[i], -1);
        }

        int max = getMax(0, 0, 0, total); // 막내 길원이가 얻을 수 있는 효용의 합의 최댓값
        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }//main

    private static int getMax(int n, int a, int b, int total) {
        if(n == N) {
            int k =  total - a - b;
            if(a >= k && b >= k) return k;
            
            return 0;
        }
        if(dp[a][b] != -1) return dp[a][b];

        int max = 0;
        if(a + V[n] <= total) max = Math.max(max, getMax(n+1, a+V[n], b, total));
        if(b + V[n] <= total) max = Math.max(max, getMax(n+1, a, b+V[n], total));
        max = Math.max(max, getMax(n+1, a, b, total));

        return dp[a][b] = max;
    }//getMax

    private static void init() {
        V = new int[N];
    }//init

}//class