[백준] 14501번 - 퇴사 [Java]

https://www.acmicpc.net/problem/14501

 

[백준] 14501번 - 퇴사 [Java]

[백준] 14501번 - 퇴사 [Java]

[백준] 14501번 - 퇴사 [Java]

---

1.  아이디어

 

부분집합을 이용한 완전탐색과 다이나믹 프로그래밍 두 가지 방법으로 풀 수 있었다.

---

2. 문제풀이

 

1. 부분집합

N이 최대 15까지여서 상담을 선택하는 경우의 수가 2^15가지가 나왔다. 이정도면 완전 탐색으로도 충분하다고 생각되서 visited라는 boolean 타입 배열에 각 상담을 진행하는 경우 true, 진행하지 않는 경우 false를 저장한 후 findMax 메서드에서 해당 일정이 중복 또는 퇴사일에 맞게 가능한 일정인지 판단하고 가능한 경우면 최대 수익을 갱신하며 정답을 구했다.

 

2. 다이나믹 프로그래밍

dp 배열에는 해당일에 얻을 수 있는 최대 수익을 저장한다. dp 배열은 현재 상담을 진행했을 때 최대 수익과 진행하지 않았을 때 최대 수익을 비교 갱신하는 방식으로 동작하며 현재 얻을 수 있는 최대수익과 다음날 얻을 수 있는 최대수익을 비교 갱신해줘야 상담이 종료되지 않는 비어있는 날에도 알맞게 최대수익이 들어가게 된다. 상담 종료일은 N+1일 이어서 dp[N+1]을 출력하도록 했고 상담이 퇴사일 이후에 종료되는 것에 대한 예외처리를 간단하게 하기 위해 패딩을 뒤에 5일치를 줬다.

---

3. 코드

 

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

public class Main_PowerSet {

    private static int[] t;
    private static int[] p;
    private static boolean[] visited;
    private static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        visited = new boolean[1 + N];
        powerSet(N, 1);

        System.out.println(max);
    }

    private static void powerSet(int N, int selIdx) {
        if (selIdx > N) {
            findMax(N);
            return;
        }

        visited[selIdx] = true;
        powerSet(N, selIdx + 1);

        visited[selIdx] = false;
        powerSet(N, selIdx + 1);
    }

    private static void findMax(int N) {
        int sum = 0;
        int[] schedule = new int[1 + N];

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) continue;

            sum += p[i];
            if (i + t[i] - 1 > N) return;

            for (int j = i; j < i + t[i]; j++) {
                schedule[j]++;
                if (schedule[j] > 1) return;
            }
        }

        max = Math.max(max, sum);
    }

}

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

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

        int[] dp = new int[1 + N + 1 + 5];
        for (int i = 1; i <= N; i++) {
            dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }

        System.out.println(dp[N + 1]);
    }
}

---

4. 후기

 

1. 부분집합

2. 다이나믹 프로그래밍