[BOJ 백준] 14501번 - 퇴사 (C++ ,JAVA)

문제 :  www.acmicpc.net/problem/14501

14501번: 퇴사

난항

 

문제의 조건에서 1일부터 차례대로 생각해보려니 머리가 지끈거리기 시작하고 결국 검색의 힘을 빌리게 되었다.

검색을 해보니 브루트포스, 다이나믹 프로그래밍 두가지를 대체로 사용하는 것 같았다.

 

그리고 1일부터 생각하지 않고 반대로 제일 마지막 날부터 계산하는것을 보고 감탄했다. 난 아직 멀었다는 생각이 든다.

검색을 하면서 여러 사람들이 작성한 글을 읽어봐도 뭔가 감이 잡힐듯 하면서 코드가 짜이지 않았다.

계속 검색을 하던 중 한 블로그 글을 보게 되었는데 제일 이해가 잘되고 코드를 짜는데 많은 도움이 되었다.

 

출처 : songsunbi.tistory.com/80

백준 14501 퇴사

접근

다음과 같은 5일간의 일정표를 예로 들어보겠다.

	1일	2일	3일	4일	5일	6일
소요일 수	3	5	1	1	2	4
받는돈(금액)	10	20	10	20	15	40
최대금액	45	45	45	35	15	0

 

반대로 제일 마지막 일정부터 접근해본다.

반대로 접근한다는것은 해당 일차까지의 최대 누적 금액를 알아보겠다는 의미이다.

반대로 접근할때 6일차의 최대 금액은 ( 1 ~ 6일까지의 최대 금액이 아닌 6일차만 했을 경우이고)

5일차의 최대 금액은 (1~5일까지의 최대금액이 아닌 5~6일까지의 최대금액을 의미한다.)

 

6일차 : 소요일수가 4일이라 퇴사일을 넘기게 된다. 일을 마무리 할 수 없으므로

6일차만 진행할 경우의 최대 보수는 0이다. 마지막날은 소요일 수가 1일이 아닐경우 최대 금액이 무조건 0이라 봐야한다.

 

5일차 : 소요일수가 2일이라 퇴사 직전날에 딱 일을 끝낼 수 있다.

여기서 2일소요되는 일을 하게 되면 6일차 일은 진행할 수 없으므로 5일차 일을 진행할때 금액과, 5일차 일을 진행하지 않고 6일차를 진행하였을때 금액과 비교해야한다.

 

해당 일차의 소요일수가 퇴사까지 남은 잔여일수보다 크지 않으면 6일차의 최대금액과 5일차 금액, 5일차일을 마무리한 날의(5일로부터 2일 경과된 7일) 최대 금액의 합 중 큰 값을 비교해야 한다.

 

즉 -> max(6일차 최대금액,5일차금액+7일차최대금액(5일차 + 5일차소요기간 2일 = 7일째의 최대금액))

여기서 6일차 최대금액은 0이었고, 5일차금액인 15 + 7일차(퇴사일)최대금액 0 => 0,15중 큰 값인 15가 5일차의 최대 금액이 된다.

 

왜 비교하냐면 5일차의 기간동안 일하고 받은돈보다 그 이후 일차까지의 최대 금액이 더 크면 굳이 5일차에 일을 안해도 되기 때문에!

 

만약 해당 일차의 소요일수가 퇴사까지 남은 잔여일수보다 크다면 6일차의 최대 금액을 그대로 가져오면 된다.

(소요일수가 퇴사까지 남은 기간보다 길면 퇴사전까지 일을 마무리하지 못하기 때문)

 

4일차 : 소요일수가 1일이라 당일에 끝낼 수 있다. 기존 5일차의 최대 금액 15에 4일차의 금액 20을 더한다.

4일차까지 진행할 경우의 최대 금액은 35이다.

 

3일차 : 소요일수가 1일이라 당일에 끝낼 수 있다. 기존 4일차의 최대 금액 35에 3일차의 금액 10을 더한다.

3일차까지 진행할 경우의 최대 금액은 45이다.

 

2일차 : 앞선 5일차와 마찬가지로 퇴사 전에 일을 마무리 할 기간은 되지만, 2일차 일을 하여 받는 금액을 3일차까지 일을 해서 받은 누적 금액과 비교해야 한다.

 

2일차의 소요기간은 5일인데 2일차로부터 5일이 지나면 퇴사하는 날(7일)이 되므로 2일차를 진행할때 금액 + 7일차 최대금액인 0을 더하면 20이 되고,

3일차까지의 최대 금액인 45와 비교하여 45가 더 크므로 2일차의 최대금액은 45이다.

즉, 2일차는 안하는게 더 이득이다.

 

1일차 : 2일차와 마찬가지로 비교를 해봐야한다.

1일차의 소요기간은 3일인데 3일 후인 4일차의 최대금액 + 1일차의 금액과 2일차의 최대금액을 비교하여 큰 값이

1일차의 최대금액이 된다.

 

4일차 최대금액 35 + 1일차금액 10은 45이고 2일차 최대금액도 45이므로 둘다 45로 같다.

그래서 그대로 기존 2일차 최대금액인 45가 1일차의 최대금액이 된다.

 

1일차 최대금액이 곧 정답이 된다. 혹은 제일 마지막 일차 부터 최대 금액 연산을할때 max값을 저장해도 된다.

 

C++

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int i,j;
    int l[18],c[18],r[18] = {0,};

    cin >> i;
    for(j = 1; j<=i; j++){
        cin>>l[j]>>c[j];
    }

    for(j=i; j>0; j--){
        if(l[j]>i-j+1) r[j] = r[j+1];
        else r[j] = max(c[j] + r[j+l[j]],r[j+1]);
    }

    cout << r[1];
}

 

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int day = Integer.parseInt(br.readLine());
        int[] run_day = new int[20];
        int[] pay = new int[20];
        int[] dp = new int[20];

        for(int i=1; i<=day; i++){
            String[] input = br.readLine().split(" ");
            run_day[i] = Integer.parseInt(input[0]);
            pay[i] = Integer.parseInt(input[1]);
        }

        for(int i = day; i>0; i--){
            if(run_day[i]>day-i+1){
                dp[i] = dp[i+1];
            }else {
                dp[i] = Math.max(pay[i]+dp[i+run_day[i]],dp[i+1]);
            }
        }

        System.out.print(dp[1]);
    }
}

 

C++ : github.com/devdinist/BOJ_Code/blob/master/Cpp/DP/BOJ14501.cpp

devdinist/BOJ_Code

JAVA : github.com/devdinist/BOJ_Code/blob/master/Java/Sort_Algorithm/DP/BOJ14501.java

devdinist/BOJ_Code