[BOJ] 백준 14501 퇴사

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

7

3 10

5 20

1 10

1 20

2 15

4 40

2 200

 

 Output 

45

소요기간이 무작위로 주어지기 때문에 남은 N일 동안 모든 상담을 할 수 없습니다.

ex) [1일]에 잡혀 있는 상담은 총 3일이 걸리며, [2일]~[4일] 일정을 잡지 못해서 금액은 10입니다.

      [1일], [4일], [5일]을 선택하여, 10 + 20 + 15 = 45가 최대 수익이 됩니다.

 

문제 조건 중 상담 기간(Ti)에 따라 다음날의 상담이 안될 수 있기 때문에 

Sub Problem을 뒤에서 부터 시작합니다. dp[N-1] → dp[0] 도출

(※ N이 크지 않은 수이기 때문에 Brute Force로도 처리 가능)

dp[i] = i일 부터 상담을 시작하여 받을 수 있는 최대 금액 정보

▶ dp[i] = Max (dp[i+1] , pay[i] + dp[i + T[i]])

dp[i+1]

    - 해당 일자를 선택하지 않은 경우.

pay[i] + dp[i + T[i]]

    - 해당 일자를 선택하여 소요기간 동안 다른 상담을 할 수 없는 경우.

▶ 해당 일자 상담을 선택하는 경우와 아닌 경우로 구분.

[① 6일], [② 7일]은 상담 기간이 퇴사 이후까지 이어지므로 잡을 수 없는 상담입니다.

▶ dp[6] = 0, dp[5] = 0

[③ 5일]에서는 상담을 하는 것이 좀 더 수익을 낼 수 있습니다.

▶ dp[4] =  Max( dp[5], pay[4] + dp[6] ) = Max (0 , 15 + 0) = 15

[④ 3일], [⑤ 4일]에서도 동일한 방식으로 도출

[⑥ 2일]에서는 상담을 진행하지 않는 것이 좀 더 이익을 낼 수 있습니다.

▶ dp[1] = Max( dp[2] , pay[1] + dp[6] ) = Max( 45 , 20 + 0 ) = 45

[⑦ 1일] 일자를 선택하든 안하든 결과는 cost = 45로 동일합니다.

dp[0] = Max( dp[1] , pay[0] + dp[3] ) = Max( 45 , 10 + 35 ) = 45

 

최대이익을 묻는 문제이기 때문에 구체적인 상담 일정이 중요하지는 않습니다.

상담일자를 {1, 4, 5}를 하거나 {3, 4, 5}를 선택했을 때 cost = 45라는 최대 이익을 낼 수 있습니다.

 

 

I/O 예제

예제 #1

- [7일]~[10일]까지의 상담은 퇴사이후에도 상담이 진행되어야 하므로 진행할 수 없음.

- [5일]~[2일]상담은 [6일]자 상담을 하는 것보다 이익이 낮으므로 선택되지 않습니다.

▶ [1일], [6일] 상담을 통해 cost = 20 최대 수익이 발생합니다.

　

예제 #2

마지막날인 [10일]은 퇴사 이후에 진행되어야 하므로 cost = 0

dp[i] = Max (dp[i+1] , dp[i] + dp[i + T[i]]) 를 이용해 dp[0] 도출

[1일], [6일], [8일] 선택하였을 때,  cost = 90 최대 수익　

 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = Integer.parseInt(sc.next());
        int[] time = new int[N];
        int[] pay = new int[N];
        
        for(int i=0; i<N; i++) {
            time[i] = Integer.parseInt(sc.next());
            pay[i] = Integer.parseInt(sc.next());
        }
        
        
        int[] dp = new int[N];
        
        // 초기값 설정
        // 마지막날 상담소요시간이 이틀 이상이면 '0'
        // 소요시간이 하루라면 우선은 진행(아직 최대이익인지는 확신할 수는 없다.)
        if(time[N-1] >= 2) {
            dp[N-1] = 0;    
        }else {
            dp[N-1] = pay[N-1];
        }

        for(int i=N-2; i>=0; i--) {
            // 퇴사기간내 가능한 상담 중에서 해당 일자 상담 선택 여부 결정
            if(i + (time[i]-1) < N) {
                int elapsedTime = 0;
                if(i + time[i] < N) {
                	elapsedTime = dp[i + time[i]];
                }
                dp[i] = Math.max(dp[i+1], pay[i] + elapsedTime);
            }
            else { // 퇴사 이후 진행되는 상담인 경우
                dp[i] = dp[i+1];
            }
        }

        System.out.println(dp[0]);
            
    }
}