33.퇴사

📍 문제 설명

 

💡 접근

i번째 날부터 마지막 날까지 낼 수 있는 최대 이익을 담는 dp 테이블을 선언한다.

상담하는데 걸리는 시간이 기간안에 끝나는지에 따라 처리를 해준다.

기간안에 끝나면 현재의 이익을 과 현재 상담이 끝난 이후 날짜의 이익들을 더한값과

현재까지의 저장되어 있는 최대 이익을 비교하여 큰 값으로 갱신한다.

기간안에 끝나지 않으면 저장되어 있는 최대 이익을 dp 테이블에 담는다.

 

예를 들어 2일 째의 상담을 하게 되면 6일부터 상담진행이 가능(20+0)하기때문에

현재까지의 최대 이익인 3,4,5일(10+20+15) 상담으로 값을 갱신한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int maxValue;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        //상담하는데 걸리는 시간
        int[] t = new int[n];
        //상담완료 후 받는 돈
        int[] p = new int[n];
        for(int i = 0; i < n; i++) {
            t[i] = kb.nextInt();
            p[i] = kb.nextInt();
        }


        //dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
        //7일 ~ 마지막 날 상담
        //time = t[6] + 6 = 8 상담 불가 dp[6] = 0;
        //6일 ~ 마지막 날 상담
        //time = t[5] + 5 = 9 상담 불가 dp[5] = 0;
        //5일 ~ 마지막 날 상담
        //time = t[4] + 4 = 6 6 <= 7 상담 가능 dp[4] = 15 + dp[6] = 15 5일 상담 maxValue = 15(5일까지의 최고 이익은 15)
        //4일 ~ 마지막 날 상담
        //time = t[3] + 3 = 4 4 <= 7 상담 가능 dp[3] = 20 + dp[4] = 35(4,5일 상담) or 15(5일 상담) = 35 4,5일 상담 maxValue = 35
        //3일 ~ 마지막 날 상담
        //time = t[2] + 2 = 3 3 <= 7 상담 가능 dp[2] = 10 + dp[3] = 45(3,4,5일 상담) or 35(4,5일 상담) = 45 3,4,5일 상담 maxValue = 45
        //2일 ~ 마지막 날 상담
        //time = t[1] + 1 = 6 6 <= 7 상담 가능 dp[1] = 20 + dp[6] = 20(2일 상담) or 45(3,4,5일 상담) = 45 3,4,5일 상담 maxValue = 45
        //1일 ~ 마지막 날 상담
        //time = t[0] + 0 = 3 3 <= 7 상담 가능 dp[0] = 10 + dp[3] = 45(1,4,5일 상담) or 45(3,4,5일 상담) = 45 1,4,5 or 3,4,5일 상담 둘다
        int[] dp = new int[n+1];
        for(int i = n - 1; i >= 0; i--){
            //상담하는데 걸리는 시간
            int time = t[i] + i;
            System.out.println(time);
            //상담이 기간 안에 끝나는 경우
            if (time <= n) {
                System.out.println("1 : " + (p[i] + dp[time]));
                System.out.println("2 : " + maxValue);
                //현재 까지의 최고 이익 계산
                dp[i] = Math.max(p[i] + dp[time], maxValue);
                maxValue = dp[i];

            }
            //상담이 기간을 벗어나는 경우
            else dp[i] = maxValue;
            System.out.println();
        }
        System.out.println(Arrays.toString(dp));
    }
}