[Silver III][JAVA] 14501번:퇴사

DP 풀이과정

• 날짜의 끝 부터 첫 날 까지 거꾸로 DP 배열을 구해나간다.
• 배열 DP[i]는 날짜i부터 상담을 했을 때 벌 수 있는 돈의 최댓값이다.
  예를 들어 DP[5] 라면 5일 부터 일 한 값 중 최댓값이다.
  그러므로 DP[1] 을 구해주면 된다.
• i + T[i] > N + 1 라면 i 날짜에는 일을 할 수 없다.
  따라서 DP[i] 의 값은 DP[i + 1] 이 된다.
  i의 날짜에 i의 일을 하지 못한다면i + 1의 날짜부터 일해서 번 돈의 최댓값과 i 의 날짜부터 일해서 번 돈의 최댓값이 같기 때문이다.
• i + T[i] <= N + 1 라면i날짜에 일을 할 수 있다.
  일을 하지 않았을 때의 값 DP[i + 1]
i 날짜의 일을 하면 i 날짜의 페이인 P[i] 와 i 날짜 이후에 번 돈의 최댓값인 DP[i+T[i]] 의 합인 값 P[i] + DP[i+T[i]]
  위의 DP[i + 1] 과 P[i] + DP[i+T[i]] 값 중 더 큰 값을 DP[i]에 넣어준다

정리

DP를 사용할 때 뒤에서부터 시작하는 것도 좋은 방법이다.

코드

package baekjoon_java.SilverIII;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
https://www.acmicpc.net/problem/14501
14232KB 132ms
다이나믹 프로그래밍
 */
public class 퇴사 {
    public static void main (String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int []T = new int[N+1];
        int []P = new int[N+1];
        int[] DP = new int[N+2];

        for(int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = N; i > 0; i--) {
            int next = i + T[i];// 다음 날짜
            if(next > N + 1) {// 일할 수 있는 날짜를 넘어가는 경우
                // 일을 하지 못하므로 바로 다음 DP값(더 앞쪽의 날짜)로 설정
                DP[i] = DP[i + 1];
            }else {
                // 일할 수 있는 날짜인 경우
                // 1. 일하지 않았을 때(DP[i + 1])
                // 2. 일 했을 때 총 벌 수 있는 금액(P[i] + DP[next])
                // 위 두 경우 중 더 큰 값을 DP에 넣어준다.
                DP[i] = Math.max(DP[i + 1], P[i] + DP[next]);
            }
        }
        System.out.println(DP[1]);
    }
}