[Java/알고리즘] 백준 19645 | 햄최몇?

백준 19645 햄최몇?

0. 메모리 및 실행시간

1. 제출 코드

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

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());
        st = new StringTokenizer(br.readLine());

        int total = 0;
        int[] values = new int[N];
        for (int i = 0; i < N; i++) {
            values[i] = Integer.parseInt(st.nextToken());
            total += values[i];
        }
        
        // dp 배열 선언
        // dp[i][j] = true --> A의 무게가 i이고, B의 무게가 j인 경우를 만들 수 있다
        boolean[][] dp = new boolean[total+1][total+1];
        dp[0][0] = true;
        
        int curSum = 0;
        for (int i = 0; i < N; i++) {
        	curSum += values[i];
        	// 현재까지 버거 가치의 합은 curSum
        	// 그 이하를 돌면서 작은 값으로 합 맞추기가 가능했던 이전 배낭들을 찾아가자
        	for (int a = curSum; a >= 0; a--) { // A 버거 합
        		for (int b = curSum; b >= 0; b--) { // B 버거 합
        			if (dp[a][b]) {
        				dp[a+values[i]][b] = true; // A에게 주는 경우
        				dp[a][b+values[i]] = true; // B에게 주는 경우
        			}
        		}
        	}
        }
        
        // 최적해 찾기
        int ans = 0;
        for (int i = 0; i < total+1; i++) {
        	for (int j = 0; j < total+1; j++) {
        		if (dp[i][j]) {
        			// 세 개의 가치 중 가장 작은 가치 (우리가 찾고자 하는 가장 작은 배낭의 가치)
        			int curMin = Math.min(total-i-j, Math.min(i, j));
        			ans = Math.max(curMin, ans);
        		}
        	}
        }

        System.out.println(ans);
        br.close();
    }
}

2. 풀이과정 및 리뷰

• 문제 접근: 여러 사람의 도움으로 ……. 날먹 맛있다~
• 시간복잡도: $O(N*total^2)$
• 풀이과정 💡 **메인 아이디어** --- - 세 사람의 효용을 모두 저장할 필요 없다. - 두 사람의 효용이 정해지면 나머지 한 사람의 효용은 자동으로 결정됨. - → 2차원 배열을 이용하자 - `values` 배열에 값을 입력받으면서 값들의 총 합을 `total` 변수에 저장하기 - total +1 사이즈의 2차원 DP 배열 (boolean) 선언하자 - `curSum` 변수에 햄버거의 효용을 하나씩 더하면서 - A의 버거합 a, B의 버거합 b를 `curSum`부터 0까지 이중 for문으로 돌면서 - `dp[a][b] = true`라면 → `dp[a+현재 버거의 효용][b] = true`, `dp[a][b+현재 버거의 효용] = true` - 의미 : 현재까지의 효용의 합보다 작은 값들을 순회하면서, 합 맞추기가 가능했던 이전 배낭들을 찾아가자 → 각 가방에 현재 버거의 효용을 넣는 경우 두 가지를 true 처리 - dp 배열을 순회하면서 `dp[i][j] = true` 라면 → “i, j, (total-i-j) 세 값으로 효용을 나눌 수 있다” - 세 효용 중 최솟값이 가장 큰 경우로 `ans` 변수 갱신
• 개선점

  ✅ (1) Rolling Array (이전 상태만 유지)

  현재 DP는 모든 단계를 누적하지만, 사실상 이전 단계의 결과만 사용합니다. → 따라서 다음과 같이 2중 배열 → 1중 배열로 압축할 수 있습니다.

  💡 아이디어

  boolean[][] dp = new boolean[total+1][total+1];
  boolean[][] next = new boolean[total+1][total+1];
  
  for (int i = 0; i < N; i++) {
      for (int a = 0; a <= total; a++) {
          for (int b = 0; b <= total; b++) {
              if (!dp[a][b]) continue;
              next[a+values[i]][b] = true;
              next[a][b+values[i]] = true;
              next[a][b] = true; // 현재 안 넣는 경우
          }
      }
      dp = next;
      next = new boolean[total+1][total+1];
  }

  이렇게 하면 이전 단계만 유지하므로 O(total²) 메모리는 그대로지만, 덮어쓰기 위험 없이 더 명확해지고 curSum 없이도 동작합니다.

  ---

  ✅ (2) Bitset 사용 (고급 최적화)

  Java의 boolean은 실제로 1바이트씩 차지하지만, BitSet은 비트 단위로 관리합니다. 즉, 8배의 메모리 절감 가능.

  BitSet[] dp = new BitSet[total+1];
  for (int i = 0; i <= total; i++) dp[i] = new BitSet(total+1);
  dp[0].set(0);

  다만, BitSet은 비트 단위 연산이 빠르지만 구현 복잡도가 조금 올라갑니다.

  ---

  ✅ (3) 탐색 범위 축소 (curSum 활용 정확화)

  현재 코드의 내부 루프:

  for (int a = curSum; a >= 0; a--) {
      for (int b = curSum; b >= 0; b--) {

  → 실제로 a와 b가 curSum보다 훨씬 작아야 의미가 있음. a+b > curSum인 경우는 존재 불가이므로 불필요한 탐색입니다. 이를 줄이면 여전히 O(N × total²)이지만, 상수 배 수준의 실제 시간 단축이 가능.

  ---

  ✅ (4) Symmetry (대칭성) 활용

  dp[a][b]와 dp[b][a]는 사실상 같은 의미입니다. 즉, a ≤ b만 계산해도 결과는 같습니다.

  for (int a = curSum; a >= 0; a--) {
      for (int b = a; b >= 0; b--) { // 절반만 탐색

  이렇게 하면 실제 연산량을 절반으로 줄일 수 있습니다.