이코테 - 퇴사 with JAVA

 

 

해결

만약, 아래와 같은 표가 있다고 가정하자

첫번째 줄은 걸리는 날, 두번째 줄은 받는 돈이다.

5	5	5	5	5	5	5	5	5	5
10	9	8	7	6	10	9	8	7	6

인덱스 9에 위치한 스케줄부터 인덱스6에 위치한 일은 할 수 없다.

인덱스 5에서는 일을 할 수 있고 인덱스 10부터 다시 일할 수 있다. 하지만 10은 존재하지 않으므로 여기까지 가장 많이 벌 수 있는돈은 10이다.

인덱스1부터 4까지는 일은 할 수 있지만 일을 하게되면 인덱스 5에 위치한 일을 할 수 없다. 따라서 돈을 최대한으로 벌려면 해당 인덱스들에서는 일을 하지 않아야 한다.

인덱스 0에서 일을하면 인덱스 5부터 다시 일을 할 수 있다.

 

 

또한, 항상 DP에서는 전의 값이 현재 값의 영향을 끼치는 형태고 기존의 리스트의 값을 이용해서 이를 표현했다.

여기서는 새로운 변수를 만들어 값을 할당하는 것이 오히려 이해가 쉽다.

 

 

 

 

 

코드

import java.util.*;

public class Q3 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> times = new ArrayList<>();
        List<Integer> costs = new ArrayList<>();
        for(int i=0; i<n; i++){
            int time = sc.nextInt();
            int cost = sc.nextInt();
            times.add(time);
            costs.add(cost);
        }
        int max_value = 0;
        int[] dp = new int[n+1];
        for(int i=n-1; i>=0; i--){
            int time = times.get(i)+i;
            int cost = costs.get(i);
            if(time <= n){
                dp[i] = Math.max(dp[time]+cost, max_value);
                max_value = dp[i];
            }
            else{
                dp[i] = max_value;
            }
        }
        System.out.println(max_value);
    }
}