백준(BOJ) 15486 퇴사2

퇴사1 문제와의 차이점 동영상보고 기록해 놓기:

 

 

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

 

 

어떻게 현실적으로 이 문제를 보고 어떻게 "이문제는 DP로 풀어야 한다"라고 떠올릴 수 있는 것인가? 우선은 해본다. 아래 그림과 같이 그려보는것이다. 1,2,3일째는 모두 그 이득이 0이다. 그런데 1일차에 있는 일을 하게 되면 그 이득으로 4일 차에 10을 얻게 된다. 마찬가지로 2일차의 일을 하게 되면 그 이득으로 7일차에 20의 이득을 얻게 된다. 이렇게 차근차근 표시해 나가는 것이다 우선은. 마찬가지로 3일차에 해당하는 일을 하게 되면 4일 차에 10의 이득을 얻게 된다. 그런데 이미 4일차에는 1일차에 해당하는 일을 했을때 얻을 수 있는 이득이 있다. 그러므로 1일차에 일을 하여 얻는 이득과 3일차에 얻는 이득을 서로 싸우게 하여 더 큰것이 4일차의 값이 되게한다. 여기서!!! 이전에 사용하였던값인 1일차에 해당하는 이득이라는 이전에 기록되었던값을 새로운 이득인 3일차에 해당하는 일을 하게 되었을때 4일차에 얻는 이득과 싸우게 하므로, 다시 말하면 이전에 사용한 값(1일차에 해당하는 이득)을 싸우는데 다시 사용하게 되므로 dp라는것을 눈치 긁을 수 있는 것이다. 이전에 사용했던 값을 재사용한다면 DP를 사용하는 것을 생각해 볼수 있다.

 

비슷비슷한 문제일지라도 문제의 조건과 무엇을 구하는지에 따라 설계기법이 달라진다.
마감시간과 작업일수가 있는 스캐줄링 에서 최소시간외 근무일수(27112, 시간외 근무 멈춰). 단 안되면 그냥 -1출력 =>Greedy

마감시간이 있는 스케줄링에서 최대이익(작업일수 없음, 마감시간과 이득만 있음) => Greedy

(퇴사2문제)작업일수가 있는 스케줄링에서 최대이익 (작업일수, 이득만 있음) =Dynamic

https://www.youtube.com/watch?v=-4wjSUr1_K0&t=1458s

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
어려운 문제다... dp의 점화식을 구하기 위해서는 무조건 규칙을 찾아 보기 위해 해보는 방법 밖에는 없다.
https://www.youtube.com/watch?v=-4wjSUr1_K0&t=1458s

비슷비슷한 문제일지라도 문제의 조건과 무엇을 구하는지에 따라 설계기법이 달라진다. 
마감시간과 작업일수가 있는 스캐줄링 에서 최소시간외 근무일수(27112, 시간외 근무 멈춰). 단 안되면 그냥 -1출력 =>Greedy

마감시간이 있는 스케줄링에서 최대이익(작업일수 없음, 마감시간과 이득만 있음) => Greedy 

(퇴사2문제)작업일수가 있는 스케줄링에서 최대이익 (작업일수, 이득만 있음) =Dynamic
 */
public class Main{
    public static void solution(int n, int[]duration, int[]profit){
        int[]dp=new int[n+2];
        for(int i=1;i<=n;i++){
            int next=i+duration[i];
            if(next<=n+1)
                dp[next]=Math.max(dp[i]+profit[i], dp[next]);

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

        }
        System.out.println(dp[n+1]);

    }

    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[]duration=new int[n+1];
        int[]profit=new int[n+1];
        StringTokenizer st;
        for(int i=1;i<=n;i++){
            st=new StringTokenizer(br.readLine());
            duration[i]=Integer.parseInt(st.nextToken());
            profit[i]=Integer.parseInt(st.nextToken());
        }
        solution(n, duration, profit);
    }
}