[백준] 14501 - 퇴사 (Java)

문제

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

1) 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번째 상담 비용 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 코드

import java.util.Scanner;

public class S14501 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[N + 2];  // 오늘부터 퇴사일까지 벌 수 있는 최대 수입
        int[] T = new int[N + 1];  // 상담에 필요한 일 수
        int[] P = new int[N + 1];  // 상담을 완료했을 때 받는 수입

        for (int i = 1; i <= N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

        for (int i = N; i > 0; i--) {
            if (i + T[i] > N + 1) { // i번째 상담을 퇴사일까지 끝낼 수 없을 때
                D[i] = D[i + 1];
            } else {
                // i번째 상담을 퇴사일까지 끝낼 수 있을 때
                // 1. 일하지 않았을 때(DP[i + 1])
                // 2. 일 했을 때(P[i] + DP[next])
                // 위 두 경우 중 max값 선택
                D[i] = Math.max(D[i + 1], P[i] + D[i + T[i]]);
            }
        }

        System.out.println(D[1]);

    }

}

2)DFS 코드