1535번: 안녕

문제

세준이는 N명의 사람에게 인사를 하려고 합니다. 각각의 사람에게 인사를 할 때 잃는 체력과 얻는 기쁨이 주어집니다. 초기 체력은 100이며, 체력이 0 이하가 되면 쓰러지게 되므로 소모하는 체력의 총합은 100보다 엄격히 작아야 합니다(1~99). 주어진 체력 내에서 세준이가 얻을 수 있는 최대 기쁨을 구하는 문제입니다.

• 입력: 첫째 줄에 사람의 수 N (1 ≤ N ≤ 20)이 주어집니다. 둘째 줄에는 각각의 사람에게 인사할 때 잃는 체력 L이 주어지고, 셋째 줄에는 얻는 기쁨 J가 주어집니다.
• 출력: 첫째 줄에 주어진 체력 내에서 얻을 수 있는 최대 기쁨을 출력합니다.

링크: https://www.acmicpc.net/problem/1535

풀이 1: 비트마스킹(1 << n)을 활용한 완전 탐색

N이 최대 20이므로 가능한 모든 조합의 수는 2^20(약 104만 개)입니다. 시간 제한(2초) 내에 충분히 탐색 가능한 수치이므로, 0부터 (1 << n) - 1까지의 정수를 활용한 비트마스킹 완전탐색으로 풀이할 수 있습니다.

• 상태 순회: i를 0부터 (1 << n) - 1까지 순회하며, 각 i의 이진수 비트를 사람들의 선택 상태(인사 여부)로 간주합니다.
• 조건 검사: 각 조합(상태 i)마다 초기 체력 hp를 100으로 두고, 선택된 사람(j번째 비트가 1인 경우)에 대해 소모할 체력을 확인합니다.
• 가지치기 (Early Exit): 만약 현재 남은 체력 hp가 소모해야 할 체력 a[j]보다 작거나 같다면(hp <= a[j]), 해당 사람에게 인사하는 순간 체력이 0 이하가 되므로 즉시 내부 반복문을 중단(break)합니다.
• 최댓값 갱신: 선택된 모든 사람에게 무사히 인사를 마쳤거나, 조건에 막혀 탐색이 중단되었을 때 그 시점까지 모인 기쁨의 합(sum)으로 전체 최댓값 ans를 갱신합니다.

코드 1

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       int[] b = new int[n];
       st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          b[i] = Integer.parseInt(st.nextToken());
       }

       int ans = 0;
       // 0부터 2^n - 1 까지 모든 상태 탐색 (비트마스킹)
       for (int i = 0; i < (1 << n); i++) {
          int hp = 100;
          int sum = 0;
          for (int j = 0; j < n; j++) {
             // j번째 사람에게 인사를 하는 경우
             if ((i & (1 << j)) != 0) {
                // 체력이 0 이하가 될 상황이면 해당 조합 탐색 중단
                if (hp <= a[j]) {
                   break;
                }
                hp -= a[j];
                sum += b[j];
             }
          }
          ans = Math.max(ans, sum);
       }

       bw.write(ans + "\n");

       bw.flush();
    }
}

풀이 2: 1차원 DP 배열을 활용한 0-1 배낭 문제(Knapsack) 풀이

사람의 수(N)가 커질 경우 비트마스킹을 통한 완전 탐색은 시간 초과가 발생합니다. 이 문제는 본질적으로 한정된 용량(체력 99) 내에서 최대의 가치(기쁨)를 담아내는 0-1 배낭 문제(0-1 Knapsack Problem)이므로, 다이나믹 프로그래밍(DP)을 사용해 O(N * K) 시간 복잡도로 효율적으로 풀 수 있습니다.

• 상태 정의: dp[j]를 소모한 체력이 j일 때 얻을 수 있는 최대 기쁨으로 정의합니다.
• 배열 크기 설정: 세준이의 체력이 0 이하가 되면 안 되므로, 최대로 소모할 수 있는 체력은 99입니다. 따라서 크기가 100인 1차원 배열 dp를 선언합니다.
• 점화식 도출: 각 사람(i)을 순회하면서 배낭(체력)의 한도 내에서 갱신합니다. 체력 j를 소모할 때, 현재 사람에게 인사하지 않는 경우(dp[j])와 현재 사람에게 인사하는 경우(dp[j - L[i]] + J[i]) 중 더 큰 값으로 갱신합니다.
• 역순 순회 주의사항: 1차원 배열을 사용하여 DP를 진행할 때는 동일한 사람이 중복으로 인사되는 것을 방지하기 위해, 체력을 순회하는 내부 반복문을 반드시 최대 체력(99)부터 내려오는 역순(j--)으로 진행해야 합니다.

코드 2

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[] L = new int[n]; // 잃는 체력
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          L[i] = Integer.parseInt(st.nextToken());
       }

       int[] J = new int[n]; // 얻는 기쁨
       st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          J[i] = Integer.parseInt(st.nextToken());
       }

       // 체력이 100이 되면 쓰러지므로, 허용되는 최대 소모 체력은 99
       int[] dp = new int[100];

       // DP 배낭 문제 (1차원 배열 최적화)
       for (int i = 0; i < n; i++) {
          // 중복 적용을 막기 위해 뒤에서부터 순회
          for (int j = 99; j >= L[i]; j--) {
             dp[j] = Math.max(dp[j], dp[j - L[i]] + J[i]);
          }
       }

       // 최대 99의 체력을 소모했을 때 얻을 수 있는 최대 기쁨
       bw.write(dp[99] + "\n");

       bw.flush();
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 비트마스킹 (Bitmasking), 배낭 문제 (Knapsack), 다이나믹 프로그래밍 (Dynamic Programming)