[SWEA] 4052 프리랜서

출처: [SWEA] SW 문제해결 심화 - 동적 계획법

 Input 

1

9 10

1 5 30

4 7 25

2 9 42

8 10 9

1 4 20

5 9 27

7 10 16

1 3 15

5 7 7

 

 Output 

#1 49

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

동적계획법(Dynamic Programming, DP)

ex) {T8, T2, T4} = {15 + 25 + 9} = 『49』로 일정이 겹치지 않게 가장 많이 돈을 버는 경우.

 

구현

먼저, 요청(Job)을 끝나는 시간을 기준 오름차순으로 정렬합니다.

(끝나는 시간이 동일한 경우 시작시간 기준 오름차순 정렬)

▶ DP[i] = 1 ~ i까지의 일정 중 일정이 겹치지 않게 가장 많이 돈을 버는 최적의 해 

① DP[1] = 신청 일정이 1개인 경우 입니다.

    이때는 무조건 선택하는 것이 최선이므로 DP[1] = 15

② DP[2] = 신청 일정이 2개입니다.

    일정이 서로 겹치지 않으면 두 개 모두 선택하면 되지만

    일정이 겹친다면 더 많은 돈이 되는 일을 선택

▶ DP[i] = Max(DP[i-1], cost[i] + DP[p(i)])

DP[i-1] : 일정 i를 선택하지 않은 경우

cost[i] + DP[p(i)] : 일정 i를 선택한 경우, 선택한 일정의 금액과 

                               선택한 일정과 겹치지 않게 소화했었던 최적의 해 DP[p(i)]를 더해줍니다.

                               만족하는 일정이 없는 경우 D[p(i)] = 0

 

P[i]에 대한 이해

DP[7]은 여섯번째 요청 [5, 9]로 해당 기간과 겹치지 않으면서 가장 마지막 요청은

5번째 요청인 [1, 4]입니다. 즉, 앞서 정렬된 요청들의 끝나는 시간이 i번째 요청의 시작시간보다 작아야 합니다.

((끝나는 시간) [1, 4] < [5, 9] (시작시간)을 만족하는 제일 마지막 요청.

※ 문제 조건상 요청이 끝나는 시간에 바로 다른 요청을 시작하지 않는다.

③ DP[3] = Max(DP[2], cost[3] + DP[p(3)]) = Max(20, 30 + 0) = 30

④ DP[4] = Max(DP[3], cost[4] + DP[p(4)]) = Max(30, 25 + DP[1]) = 40

⑤ DP[5] = Max(DP[4], cost[5] + DP[p(5)]) = Max(40, 7 + DP[2]) = 40

⑥ DP[6] = Max(DP[5], cost[6] + DP[p(6)]) = Max(40, 42 + 0) = 42

⑦ DP[7] = Max(DP[6], cost[7] + DP[p(7)]) = Max(42, 27 + DP[2]) = 47

⑧ DP[8] = Max(DP[7], cost[8] + DP[p(8)]) = Max(47, 16 + DP[3]) = 47

⑨ DP[9] = Max(DP[8], cost[9] + DP[p(9)]) = Max(47, 9 + DP[5]) = 49　

---

import java.io.*;
import java.util.*;
 
public class Solution {
    static int[] DP;
    static Job[] jobs;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
 
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
 
            jobs = new Job[N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                jobs[i] = new Job(start, end, cost);
            }
             
            Arrays.sort(jobs);
 
            DP = new int[N];
            DP[0] = jobs[0].cost;
             
            for (int i = 1; i < N; i++) {
                DP[i] = Math.max(DP[i-1], jobs[i].cost + findAlternative(i));
            }
 
            // 정답 출력
            System.out.println("#" + tc + " " + DP[N-1]);
        }
    }
 
    private static int findAlternative(int target) {
        int ret = 0;
        int idx = -1;
        for(int i=0; i < target; i++) {
            // 대상(taget)이 끝나는 시간이 이후로 시작하는 job인지 확인
            if(jobs[i].end >= jobs[target].start) {
                break;
            }
            idx = i;
        }
         
        if(idx >= 0)
            ret = DP[idx];
         
        return ret;
    }
}
 
class Job implements Comparable<Job>{
    int start, end, cost;
 
    Job(int start, int end, int cost){
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
     
    @Override
    public int compareTo(Job target) {
        if(this.end != target.end) return this.end - target.end;
        return this.start - target.start;
    }
}