[Algorithm] 퇴사

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일 째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡아달라고 부탁했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡았다.

 

각각의 상담은 완료하는데 거리는 시간 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.

 

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 구하시오.

 

풀이

1. 시간은 흐르기 때문에 앞에서부터 계산하기보다, 마지막 날부터 최고의 금액을 계산하면서 1일차로 오는 것이 좋다고 생각했다.

 

2. 1일부터 N일까지의 업무 중 X일 차에 수행할 업무가 걸리는 시간 Tx가 있을 때, X + Tx가 N일을 넘기지 않으면 해당 업무는 수행 가능하다.

 

3. 최고의 수익을 저장할 DP 테이블을 두고 최대값을 갱신하면서 풀었다.

 

결국 dp[x] = dp[x]와 dp[x + Tx] + p[x] 사이의 최대값을 구하면 된다.

그리고 dp 테이블에 저장된 값 중 가장 큰 값이 최대 수익이 된다.

 

전체 소스코드

import java.util.*;

public class Main {

    public static int n;

    public static int[] p = new int[15];
    public static int[] t = new int[15];
    public static int[] dp = new int[15];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            t[i+1] = sc.nextInt();
            p[i+1] = sc.nextInt();
        }
        
        
        int result = 0;
        for (int i = n; i > 0; i--) {
            if (i + t[i] <= n+1) {
                dp[i] = Math.max(dp[i], dp[i+t[i]] + p[i]);
            }
            result = Math.max(result, dp[i]);
        }

        System.out.println(result);

    }
        
}