[PS/Java] BOJ14501 - 퇴사

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
퇴사	BOJ	Silver 4	DP, Brute Force	풀이	문제

풀이

• 오늘부터 N + 1일째 되는 날 퇴사합니다.
• N일 동안(퇴사까지) 최대한 많은 상담을 합니다.
• 하루에 하나씩, 서로 다른 사람의 상담이 잡혀 있습니다.(input)
• 각각의 상담은 상담을 완료하는 데 걸리는 시간 $T_i$와 상담을 했을 때 받을 수 있는 금액 $P_I$으로 이루어져 있습니다.
• 입력이 주어졌을 때 최대 수익을 구해야 합니다.

점화식

현재 날짜에서 소요 시간($T_i$)과 금액($P_i$)를 더해 dp에 저장합니다.
$dp[i + T[i]] = Math.math(dp[i + T[i]], dp[i] + P[i])$

Case 1 : DP

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 다이나믹 프로그래밍, 브루트포스 알고리즘
 * Silver 4
 * 퇴사
 * https://www.acmicpc.net/problem/14501
 */
public class BOJ_14501_퇴사 {

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

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

        // dp : N일에 얻을 수 있는 최대 수익
        int[] dp = new int[n + 2];
        int[] T = new int[n + 1];
        int[] P = new int[n + 1];

        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 maxProfit = calcMaxProfit(n, T, P, dp);

        System.out.println(maxProfit);
    }

    private static int calcMaxProfit(int n, int[] T, int[] P, int[] dp) {

        for (int i = 1; i <= n; i++) {
            // 다음 날을 현재 날짜와 비교하여 최대값을 갱신
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);

            // 현재 날짜에서 소요시간을 더한 값이 N + 1(퇴사 날)을 넘기는 경우
            if (i + T[i]  > n + 1) continue;

            // 1. 현재 날짜에서 현재 일정 소요 시간을 더한 날(현재 주어진 소요 시간이 끝나는 날)에
            // 2. 현재 날짜에서의 최대 이득과 현재 일정 이득으로 얻을 이득을 더한 값과
            // 3. 1의 날짜에 잡혀있던 최대 이득을 비교하여 최대값을 넣습니다.
            dp[i + T[i]] = Math.max(dp[i + T[i]], dp[i] + P[i]);
        }

        return dp[n + 1];
    }
}

Case 2 : DFS

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 다이나믹 프로그래밍, 브루트포스 알고리즘
 * Silver 4
 * 퇴사
 * https://www.acmicpc.net/problem/14501
 */
public class BOJ_14501_퇴사_DFS {
    private static int n, maxProfit = -1;
    private static int[] T, P;

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

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

        T = new int[n + 1];
        P = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());

            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        dfs(1, 0);

        System.out.println(maxProfit);
    }

    private static void dfs(int index, int profix) {
        if (index >= n + 1) {
            maxProfit = Math.max(maxProfit, profix);
            return;
        }

        if (index + T[index] <= n + 1)
            dfs(index + T[index], profix + P[index]);
        else
            dfs(index + T[index], profix);
        dfs(index + 1, profix);
    }

}