[SWEA]프리랜서의 일정 정하기 - SWEA4052

문제

• 참고 : SWEA4052

풀이

먼저 정렬을 통해서 DP를 사용할 수 있게끔 만드는 것이 중요!!

코드

package ProblemSolution.DP_Detail;

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

/**
 * 우선, 끝나는 날짜 기준 오름차순 정렬 및 동일시 시작시간 기준 오름차순 정렬
 * => 이를 통해서 일정 j는 전체 일정 중 j번째로 마치는 일정으로 볼 수 있다.
 * => 따라서 일정 j때 최적해 DP[j] 를 기록해 나갈 수 있다.
 * `OPT[j] = max ( OPT[j-1], w[j] + OPT[p(j)] )`
 * * OPT[j-1] : 일정 j 선택X
 * * OPT[p(j)]+w(j) : OPT[p(j)]는 p(j)<j인 일정들 중 젤 큰 index의 최적해(OPT) 값
 *   * p(j) : 일정 j와 겹치지 않고, j와 가장가까운(큰) 일정을 의미
 *   * w(j) : 일정 j의 비용
 */
public class 프리랜서_SWEA4052 {
    static List<Node> inArr;
    static int[] dp = new int[505];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stk;
        int T = Integer.parseInt(br.readLine());
        for(int t = 1 ; t<=T;t++) {
            // init
            sb.append('#').append(t).append(' ');
            inArr = new ArrayList<>();
            for(int i = 0 ; i<505; i++) dp[i] = 0;
            // input
            stk = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(stk.nextToken());
            int M = Integer.parseInt(stk.nextToken());
            for(int i = 0 ;i < N;i++) {
                stk = new StringTokenizer(br.readLine(), " ");
                int si = Integer.parseInt(stk.nextToken()); // 시작 날짜
                int ei = Integer.parseInt(stk.nextToken()); // 끝 날짜
                int ci = Integer.parseInt(stk.nextToken()); // 비용
                inArr.add(new Node(si,ei,ci));
            }
            // run
            Collections.sort(inArr, Node::compare); // sort
            dp[0] = inArr.get(0).c; // dp init
            for(int i = 1 ; i<N; i++) {
                int pre = 0;
                int preIdx = -1;
                for(int j = i-1 ; j>=0; j--) { // 가장 i와 가까운 idx 구하게끔 접근
                    // 겹치지 않는지 확인
                    if(inArr.get(j).e < inArr.get(i).s) {
                        preIdx = j;
                        break;
                    }
                }
                if(preIdx == -1) pre = 0;
                else pre = dp[preIdx];
                dp[i] = Math.max(dp[i-1], inArr.get(i).c+pre);
            }
            sb.append(dp[N-1]);
            sb.append('\n');
        }
        // output
        System.out.println(sb);
    }
    static class Node {
        int s, e, c;
        public Node(int s, int e, int c) {
            this.s=s;this.e=e;this.c=c;
        }

        public static int compare(Node o1, Node o2) {
            if(o1.e==o2.e) return o1.s-o2.s; // 시작 시간 오름차순
            return o1.e-o2.e; // 끝나는 시간 오름차순
        }
    }
}