[백준] 15486 퇴사 2 - DP JAVA

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

15486번: 퇴사 2

코드설명

DP 문제입니다.

 

문제로직입니다.

 

이 문제에서 이해해야할점은,

- 가장 많은 수익을 얻는 방법을 찾는것이기에 어떤 일을 한뒤, 다른 일을 하기전까지 아무일도 하지 않고 넘어갈 수 있다는 점입니다.

- 퇴사일날까지 일을 마치면 되기에 dp의 범위는 dp = new int[N+2] 입니다. (저는 dp의 idx가 1부터 시작하므로 N+2 입니다. )

 

 

위의 말을 이해한다면 쉽게 이해할 수 있습니다.

 

문제예시와 함께 설명해보겠습니다.

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

 

 

 

MAX : 각 날짜에서 일했을때의 최대일입니다. pi[i] 는 현재 일했을때의 일의 양입니다.

아래의 배열은 DP[] 배열로써 각 날짜별로 최대로 일할 수 있는 일의 양입니다.

1. MAX:0 pi[i]:50
 0 0 0 0 0 50 0 0 0 0 0
2. MAX:0 pi[i]:40
 0 0 0 0 0 50 0 0 0 0 0
3. MAX:0 pi[i]:30
 0 0 0 0 0 50 0 0 0 0 0
4. MAX:0 pi[i]:20
 0 0 0 0 0 50 0 0 0 0 0
5. MAX:0 pi[i]:10
 0 0 0 0 0 50 0 0 0 0 0
6. MAX:50 pi[i]:10
 0 0 0 0 0 50 60 0 0 0 0
7. MAX:60 pi[i]:20
 0 0 0 0 0 50 60 0 80 0 0
8. MAX:60 pi[i]:30
 0 0 0 0 0 50 60 0 80 0 90
9. MAX:90 pi[i]:0
 0 0 0 0 0 50 60 0 80 0 90

 

위의 dp배열을 보면, 6번째 DP배열에서 MAX 값이 50으로 변합니다. 이유는, 해당 6일째날에 가장 많이 일할 수 있는 일의 양이 50입니다. 

이후에 7일째날로 이동하면, 해당 날짜에서 가장 많이 일할 수 있는 일이 60 입니다. MAX값은 60으로 변경됩니다.

그리고 만약 7일째에서 입력에시에서 보면 2일 일하고 20을 일할 수 있으므로 8일째에 80 으로 dp배열이 변한 것을 볼 수 있습니다.

이제 8번째 날짜를 보면, 해당 날짜에서 3일을 일하면 마지막 퇴사일까지 90의 일을 할 수 있습니다. 

결국, 1일 + 6일 + 8일 의 일을 하는것이 최대입니다. ( 여기서 1+6+ 7일의 일을 할경우 80의 일밖에 하지 못합니다. )

문제의 MAX 값을 해당 날짜가 지날때마다 UPDATE 시켜주어야만 문제의 로직이 성립합니다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int T, N, M;
	public static long answer = 0;
	public static int[] arr;
	public static int[] ti;
	public static int[] pi;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+2];
    	ti = new int[N+2];
    	pi = new int[N+2];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		ti[i] = Integer.parseInt(st.nextToken());
    		pi[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	int Max = 0;
    	for(int i=1;i<=N+1;i++) {
    		Max = Math.max(Max , dp[i]);
    		
    		int movedIdx = i + ti[i]; //상담을 완료한 날짜 
    		if(movedIdx <= N + 1) { //퇴사일까지 가능하므로 (N+1) 까지라면,
    			dp[movedIdx] = Math.max(Max + pi[i] ,dp[movedIdx]);
    		}
    	} 	
    	System.out.println(Max);
    }
    
}