[백준] 14501 퇴사 [java]

문제

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

생각

그리디 ?
단위 상담(하루) 당 금액이 큰 순으로 정렬해서 풀어볼까 했지만, 상담을 쪼갤 수 없기에 그리디가 아닌 DP로 판단했다.

DP 풀이

bottom-up 방식으로 생각하다보니, 너무 어려웠다.
따라서, top-down 방식으로 풀었다.

• idx 7 : 2일이 걸리므로 상담을 진행할 수 없다.
• idx 6 : 2일이 걸리므로 상담을 진행할 수 없다.
  
• idx 5 : 2일이 걸리므로 상담을 진행할 수 있다.
  dp[6]과 P[5] + dP[5 + 2] 중 큰 것을 넣는다.
  dp[6]을 넣는다는 말은 5일차 상담을 진행하지 않는다는 말이고, P[5] + dP[5 + 2]를 넣는다는 말은 5일차 상담을 진행하겠다는 말이다.
  P[5] + P[5 + 2] : 5일부터 시작해서 2일이 걸리므로, 해당 상담을 진행한다면, 7일차 상담부터 진행 가능
  
• idx 4 : 1일이 걸리므로 상담을 진행할 수 있다.
  dp[5]과 P[4] + dP[4 + 1] 중 큰 것을 넣는다.
  
• idx 3 : 1일이 걸리므로 상담을 진행할 수 있다.
  dp[4]과 P[3] + dP[3 + 1] 중 큰 것을 넣는다.
  
• idx 2 : 5일이 걸리므로 상담을 진행할 수 있다.
  dp[3]과 P[2] + dP[2 + 5] 중 큰 것을 넣는다.
  
• idx 1 : 3일이 걸리므로 상담을 진행할 수 있다.
  dp[2]과 P[1] + dP[1 + 3] 중 큰 것을 넣는다.
  
  dp[1]이 정답이 된다.

소스코드

import java.util.Scanner;

// dp임 / 쪼갤 수 없는 보석을 정해진 무게의 가방에 담는 문제와 같다.
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] days = new int[size + 1];
        int[] moneys = new int[size + 1];
        for(int i = 1; i <= size; i++){
            days[i] = scanner.nextInt();
            moneys[i] = scanner.nextInt();
        }
        int[] dp = new int[size + 2];

        for(int i = size; i >= 1; i--){

            if(i + days[i] > size + 1){     //날짜 넘어가면 해당 상담은 할 수 없음. 포함하지 않음.
                dp[i] = dp[i + 1];
                continue;
            }

            dp[i] = Math.max(moneys[i] + dp[i + days[i]], dp[i + 1]);
        }

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