[백준] 14501번 퇴사 (JAVA)

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

14501번: 퇴사

---

 

문제를 풀고 나서 다른 사람들의 풀이를 보니 뒤에서부터 생각해서 푸는 경우도 있던데

막상 시험장이라면 생각해내지 못할 가능성이 많아 보인다.

하던데로 앞에서 푸는 방식으로 해결하는 게 연습하기는 좋을 것 같다.

 

여태까지 풀어왔던 DP방식은 INDEX를 현재 시점으로 두고 이전에 구해논 DP 값으로 비교해서 구하는 경우가 많은데

이 문제는 특이하게 구한 수익을 다음 INDEX+N 방식으로 넘겨주면서 풀어야 해서 생각하기 쉽지 않았던 것 같다.

 

그리고 주의할 점은 미래 수익을 정의하기 이전에

현재 시점의 DP 값이 이전 - 1의 DP 값보다 작으면 이전 DP로 갱신해줘야

계속 최대 수익 값이 이어지면서 원하는 날짜의 최대 수익 값을 구할 수 있다.

 

문제 해결 포인트

 

최대 수익을 이어가기

if dp[i] < dp[i-1] {

   dp[i] = dp[i-1] }

 

 

---

코드 구현

 

import java.io.*;
import java.util.*;
import java.util.function.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    static int[] dp = new int[10001];
    static int[] days = new int[10001];
    static int[] costs = new int[10001];
 
    public static void main(String[] args) throws IOException {
        int line = Integer.parseInt(br.readLine());
        int D_day = line + 1;
 
        StringTokenizer st;
        int idx = 1;
        while(line-- > 0){
            st = new StringTokenizer(br.readLine());
            int day =Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            days[idx] = day;
            costs[idx] = cost;
            idx++;
        }
 
        for(int i = 1; i<=1002; i++){
            int day = days[i]; // 현재에서 부터 진행할 날짜
            int cost = costs[i]; // 마감시 얻는 비용
 
            if(dp[i] < dp[i-1])
                dp[i] = dp[i-1];
 
            if(dp[i+day] < costs[i] + dp[i]) { // 비용 + 현재 최대치 를 미래에 입력
                dp[i + day] = costs[i] + dp[i];
            }
        }
        System.out.println(dp[D_day]);
    }
}

 

---