[백준] 19645번 - 햄최몇？ [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 햄버거를 적절하게 분배하여 길원이가 선배들보다 효용이 높지 않으면서 최대 효용을 얻어야 하는 문제다. 먼저 주어진 햄버거의 효용의 합을 구해 변수로 저장한다. 이후 2차원 방문 체크 배열을 활용해 행 인덱스와 열 인덱스가 각각 선배들이 먹은 햄버거의 효용의 합이 되게 하면 방문 체크 시 길원이가 먹은 햄버거의 효용의 합은 전체 햄버거의 효용의 합에서 선배들이 먹은 것을 빼는 것으로 구할 수 있는데 이 정보가 인덱스로 있어서 구할 수 있다.

예제 입력 1을 예로 들면 첫 햄버거인 $4$ 에 대해서는

• dp[0][0] = true -> (관우 = 0, 철환 = 0, 길원 = 4 - 0 - 0 = 4)
• dp[4][0] = true -> (관우 = 4, 철환 = 0, 길원 = 0)
• dp[0][4] = true -> (관우 = 0, 철환 = 4, 길원 = 0)

이렇게 해석할 수 있다.

다음 햄버거인 $37$ 에 대해서는

• dp[0][0] = true -> (관우 = 0, 철환 = 0, 길원 = 41 - 0 - 0 = 41)
• dp[4][0] = true -> (관우 = 4, 철환 = 0, 길원 = 41 - 4 - 0 = 37)
• dp[0][4] = true -> (관우 = 0, 철환 = 4, 길원 = 41 - 0 - 4 = 37)
• dp[37][0] = true -> (관우 = 37, 철환 = 0, 길원 = 41 - 37 - 0 = 4)
• dp[0][37] = true -> (관우 = 0, 철환 = 37, 길원 = 41 - 0 - 37 = 4)
• dp[41][0] = true -> (관우 = 41, 철환 = 0, 길원 = 41 - 41 - 0 = 0)
• dp[4][37] = true -> (관우 = 4, 철환 = 37, 길원 = 41 - 4 - 37 = 0)
• dp[37][4] = true -> (관우 = 37, 철환 = 4, 길원 = 41 - 37 - 4 = 0)
• dp[0][41] = true -> (관우 = 0, 철환 = 41, 길원 = 41 - 0 - 41 = 0)

이렇게 해석할 수 있다.

모든 햄버거에 대해 이런 과정을 진행한 후 dp 테이블에서 true 인 행, 열에 대해 길원이가 먹은 값이 행, 열 인덱스보다 작거나 같은 최댓값을 찾으면 된다. 이때 각 햄버거에 대한 탐색에 있어 같은 햄버거를 중복해서 먹지 않게 역방향 탐색을 해줘야 한다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {
    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[] arr = new int[N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sum += arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[1 + sum][1 + sum];
        dp[0][0] = true;  // 세 명 다 어떤 햄버거도 먹지 않았음
        for (int n : arr) {
            for (int i = sum; i >= 0; i--) {
                for (int j = sum; j >= 0; j--) {
                    if (dp[i][j]) {
                        dp[i + n][j] = true;
                        dp[i][j + n] = true;
                    }
                }
            }
        }

        int max = 0;
        for (int i = 1; i <= sum; i++) {
            for (int j = i; j <= sum; j++) {
                if (dp[i][j] && (sum - i - j) <= i) {
                    max = Math.max(max, sum - i - j);
                }
            }
        }

        System.out.println(max);
    }
}

2. Bottom-Up 2차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    int sum = 0;
    for (int x : v) sum += x;

    vector<vector<bool>> dp(1 + sum, vector<bool>(1 + sum));
    dp[0][0] = true;  // 세 명 다 어떤 햄버거도 먹지 않았음
    for (int x : v) {
        for (int i = sum; i >= 0; i--) {
            for (int j = sum; j >= 0; j--) {
                if (dp[i][j]) {
                    dp[i + x][j] = true;
                    dp[i][j + x] = true;
                }
            }
        }
    }

    int mx = 0;
    for (int i = 1; i <= sum; i++) {
        for (int j = i; j <= sum; j++) {
            if (dp[i][j] && (sum - i - j) <= i) {
                mx = max(mx, sum - i - j);
            }
        }
    }

    cout << mx;
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	560 ms	20772 KB	1243 B

2. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	348 ms	3036 KB	886 B

---