백준 15486 - 퇴사 2

문제

15486번: 퇴사 2

---

조건

• N+1일 째 되는 날 퇴사를 하기 위해, 남은 N일 동안 매일 상담을 하려고 노력
• 각각의 상담은 상담을 완료하는데 걸리는 시간 T, 완료 시 받을 수 있는 금액 P로 이루어짐.
• 상담을 완료하면 금액을 받는다.
• 상담 일정을 적절히 조절하여 얻을 수 최대 수익을 구해야 함.

---

접근법

• max : 현재 까지 얻은 최대 금액을 저장
• N일에 얻을 수 있는 최대 금액을 저장하는 배열 dp 생성

1일차 ( N = 1 )

1일에 얻을 수 있는 최대 금액 = 0원 → max = 0

상담을 완료하는데 걸리는 시간이 3일이므로 4일에 금액을 받을 수 있다. → dp[4] = 10

2일차

2일에 얻을 수 있는 최대 금액 = 0원 → max = 0

상담을 완료하는데 걸리는 시간이 5일이므로 7일에 금액을 받을 수 있다. → dp[7] = 20

3일차

3일에 얻을 수 있는 최대 금액 = 0원 → max = 0

상담을 완료하는데 걸리는 시간이 1일이므로 4일에 금액을 받을 수 있다. → dp[4] = 10

4일차

4일에 얻을 수 있는 최대 금액 = 10원 → max = 10

상담을 완료하는데 걸리는 시간이 1일이므로 5일에 금액을 받을 수 있다.

이때, 4일차까지 얻은 최대 금액 10원을 더해야 한다. → dp[5] = 10 + 20 = 30

5일차

5일에 얻을 수 있는 최대 금액 = 30원 → max = 30

상담을 완료하는데 걸리는 시간이 2일이므로 7일에 금액을 받을 수 있다.

이때, 5일차까지 얻은 최대 금액 30원을 더해야 한다. → dp[7] = 30 + 15 = 45

6일차

6일에 얻을 수 있는 최대 금액 = 30원 -> max = 30

상담을 완료하는데 걸리는 시간이 4일이므로 10일에 금액을 받을 수 있다.

10일에는 이미 퇴사를 하고 난 뒤이므로 계산할 필요가 없다.

7일차

7일에 얻을 수 있는 최대 금액 = 45원 → max = 45

상담을 완료하는데 걸리는 시간이 2일이므로 9일에 금액을 받을 수 있다. → 계산 의미 X

8일차 (퇴사일)

얻을 수 있는 최대 금액 = 45원

점화식

dp[상담 완료 날짜] = Math.max(dp[상담 완료 날짜], 현재날짜까지의 최대금액 + 상담 완료 금액)

---

문제 풀이

• arr : 걸리는 시간, 상담 금액을 저장하는 이차원 배열
• dp : 해당 날짜에 얻을 수 있는 최대 금액을 저장하는 배열
• max : 현재 시점까지의 최대 금액
• nextDay : 상담을 완료했을 때 금액을 받는 날짜

public class p15486 {
    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[][] arr = new int[N+2][2];
        int[] dp = new int[N + 2];

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

        int max = 0;

        for (int i = 1; i < N + 2; i++) {

            if (max < dp[i]) {
                max = dp[i];
            }

            int nextDay = i + arr[i][0];

            if (nextDay < N + 2) {
                dp[nextDay] = Math.max(dp[nextDay], max + arr[i][1]);
            }
        }

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

}