14501번: 퇴사

문제

상담원으로 일하는 백준이는 퇴사를 앞두고 남은 N일 동안 최대한 많은 상담을 하여 최대 이익을 얻으려고 합니다. 각 상담은 소요되는 시간 T_i와 받을 수 있는 금액 P_i로 이루어져 있습니다. 하루에 하나의 상담만 진행할 수 있으며, 상담이 끝나는 날까지는 다른 상담을 할 수 없습니다. 또한 N+1일째에는 퇴사를 하므로, 상담이 N일을 넘어가는 경우에는 진행할 수 없습니다.

• 입력: 첫째 줄에 N (1 ≤ N ≤ 15)이 주어집니다. 둘째 줄부터 N개의 줄에 T_i와 P_i가 주어집니다. (1 ≤ T_i ≤ 5, 1 ≤ P_i ≤ 1,000)
• 출력: 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력합니다.

풀이: 비트마스킹을 활용한 완전 탐색 (Brute Force)

상담을 '한다' 또는 '하지 않는다'의 2가지 상태가 있고, 날짜 N이 최대 15로 매우 작습니다. 따라서 발생할 수 있는 모든 경우의 수(2^15 = 32,768)를 비트마스킹으로 생성하여 시뮬레이션하는 직관적이고 확실한 풀이 방식입니다.

• 상태 순회 (비트마스킹): 0부터 (1 << n) - 1까지의 정수 i를 순회합니다. 정수 i를 이진수로 나타냈을 때, k번째 비트가 1이라면 k일째의 상담을 수행하겠다는 의미입니다.
• 유효성 검사 (check 메서드): 생성된 조합 x가 문제의 조건을 만족하는지 검사합니다.
  • 중복된 날짜에 상담이 겹치는지 확인하기 위해 크기 N의 visited 배열을 선언합니다.
  • i번째 날짜의 상담을 수행하기로 했다면((x & (1 << i)) != 0), 상담이 걸리는 T_i일 동안 visited를 true로 바꿉니다.
  • 조건 위반 판별: 만약 일정을 채우다가 퇴사일 N을 넘어가거나(i + j >= n), 이미 다른 상담이 진행 중인 날짜를 건드린다면(visited[i + j] == true), 이 조합은 불가능한 일정이므로 즉시 -1을 반환합니다.
• 최댓값 갱신: check 메서드를 무사히 통과하여 반환된 수익(sum)과 현재까지의 최대 수익(ans)을 비교하여 갱신합니다.

코드

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

public class Main {
    static int n, ans;
    static int[] t, p;

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

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

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

       // 1 << n 은 2^n. 모든 조합의 경우의 수 탐색
       for (int i = 0; i < (1 << n); i++) {
          int ret = check(i);
          ans = Math.max(ans, ret);
       }

       bw.write(ans + "");
       bw.flush();
    }

    static int check(int x) {
       int sum = 0;
       boolean[] visited = new boolean[n]; // 각 날짜의 상담 진행 여부
       
       for (int i = 0; i < n; i++) {
          // i번째 상담을 진행하기로 한 조합인 경우
          if ((x & (1 << i)) != 0) {
             
             // 해당 상담이 소요되는 시간만큼 일정 채우기
             for (int j = 0; j < t[i]; j++) {
                // 퇴사일을 초과하거나 이미 스케줄이 잡혀있다면 불가능
                if (i + j >= n || visited[i + j]) {
                   return -1;
                }
                visited[i + j] = true;
             }
             
             // 무사히 일정을 잡았다면 수익 합산
             sum += p[i];
          }
       }

       return sum;
    }
}

알고리즘 분류

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