[java 백준] 실버 3/ 14501번 퇴사

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

14501번: 퇴사

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static int N;
    public static int []T;
    public static int []P;
    public static int []dp;
 
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        T=new int[N+1];
        P=new int[N+1];
        dp=new int[N+2];
        for(int i=1;i<=N;i++){
            T[i]=sc.nextInt();
            P[i]=sc.nextInt();
        }
        for(int i=1;i<=N;i++){
            //dp[6]같이 방문하진 않지만 누적합을 위해 채워줘야 하는 경우
            dp[i]=Math.max(dp[i],dp[i-1]);
 
            if(i+T[i]<=N+1){
                // 안넣은게 더 이득일 수도
                dp[i+T[i]]=Math.max(dp[i+T[i]],dp[i]+P[i]);
            }
 
 
 
 
 
        }
 
 
        int max=0;
        for(int i=1;i<=N+1;i++){
            if(max<dp[i]){
                max=dp[i];
            }
        }
 
        System.out.println(max);
 
 
 
    }
}
 

 

dp문제 중 냅색문제 풀듯이 생각해봤다. 특정 날짜를 포함할 때랑 포함하지 않을 때 중 더 큰 값을 dp[i+T[i]]에 넣어준다.

dp[i+T[i]]=Math.max(dp[i+T[i]],dp[i]+P[i]);

dp[i+T[i]]는 이미 dp[i+T[i]]값이 존재할 때의 값과 만약 특정날짜를 포함할 때의 값 (dp[i]+p[i]) 중 더 큰 값을 비교한다.

예를 들어 입력값이

 

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

이라 해보자.

 

i는 1부터 시작을 하니까 i가 1일 때는 

dp[1+T[1]]=Math.max(dp[1+T[1]],dp[1]+P[1]) 이다.

여기서 T[1]=5를 의미하기 때문에

 

dp[6]=Math.max(dp[6],dp[1]+50) 이 된다. dp[6]은 0 dp[1]+50은 50이다. 

 

i가 2일때를 살펴보자.

 

dp[2+T[2]] 는 dp[6]이고 Math.max(dp[6],dp[2]+P[2])를 하게 되면 50과 40 중 더 큰 값을 구하는 것이므로 dp[6]=50으로 유지가 된다.

 

i가 6일 때를 보자. 

dp[6+T[6]]=Math.max(dp[7],dp[6]+P[6]) 이다. T[6]은 1이고 dp[7]은 50+10=60이 된다.

 

i가 7일 때를 보자.

이때 dp[7+T[7]]을 하게 되면서 dp의 인덱스 값이 dp[9]로 뛰게 되는데 이러면 나중에 누적합을 할때 문제가 생기면서 최대값이 잘못 나오게 된다. 이러면 최대값이 90이 안나온다.. 계속 80 나옴.

++) 왜냐면 dp[11]=dp[8]+30 이여야 하는데 dp[8]값이 없으니까 최대값 자체가 잘못 짚이는 것이다.

 

그래서 특정시간에 포함이 되지 않는, 인덱스가 넘어가지는 경우 예를 들어 dp[8] 같은 경우는 dp[8]과 dp[7]값중 더 큰 값을 넣어주면 된다. 

직관적으로 생각해보면 dp[8]은

1일 (50) + 6일(10) dp[1+5+1] 에 해당하는 값이 된다. 즉 dp[7]이다.

그래서 특정 날짜에 포함되지 않는 인덱스의 경우 이전 값을 넣어주면 된다.

그러면 dp[i]=dp[i-1]을 해주지 않으면 될까?? 라는 생각을 할 수도 있다.

하지만 dp[i]=Math.max(dp[i-1],dp[i])를 해줘야 하는 이유는!! 만약 i가 6일때를 다시 생각해보자.

이미 i가 1일 때 dp[6]=50으로 지정해줬는데 

dp[i]=dp[i-1]때문에 dp[6]=dp[5]=0으로 초기화 되어버린다..! 그래서 꼭 이전에 누적한 값을 보존해주기 위해 

Math.max로 더 큰 값을 판별하는 것이 필요하다..!