99클럽 코테 스터디 29일차 TIL

오늘의 학습 키워드

• 동적 프로그래밍 (Dynamic Programming)
• 작업 스케줄링 (Job Scheduling)
• 최적화 문제 해결

문제 이해

이 문제는 여러 작업이 주어졌을 때, 서로 겹치지 않도록 작업을 선택해 최대 이익을 얻는 문제입니다. 각 작업은 시작 시간, 종료 시간, 그리고 해당 작업을 수행했을 때 얻는 이익이 주어지며, 가능한 작업 조합 중에서 이익이 가장 큰 조합을 찾는 것이 목표입니다.

나의 풀이

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] startTime = {1, 1, 1};
        int[] endTime = {2, 3, 4};
        int[] profit = {5, 6, 4};
        System.out.println(jobScheduling(startTime, endTime, profit));
    }

    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;

        int[] memo = new int[n + 1];

        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        // 종료 시간 기준으로 정렬
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);

        for (int i = 0; i < n; i++) {
            memo[i + 1] = Math.max(memo[i], jobs[i][2]);
            for (int j = i - 1; j >= 0; j--) {
                // 종료 시간이 다음 작업의 시작 시간보다 작거나 같으면
                if (jobs[j][1] <= jobs[i][0]) {
                    int prev = memo[i + 1]; // 현재 작업까지의 최대 이익
                    int current = memo[j + 1] + jobs[i][2]; // 이전 작업까지의 최대 이익 + 현재 작업의 이익
                    memo[i + 1] = Math.max(prev, current);
                    break;
                }
            }
        }

        return memo[n];
    }
}

풀이 설명

1. 작업 정보 초기화

   • 주어진 작업의 시작 시간, 종료 시간, 이익을 jobs 배열에 저장합니다. 이 배열은 각 작업을 {시작 시간, 종료 시간, 이익}의 형태로 저장합니다.

2. 작업 정렬

   • 작업을 종료 시간 기준으로 정렬합니다. 이는 먼저 끝나는 작업을 우선 선택함으로써, 최대한 많은 작업을 선택할 수 있도록 하기 위함입니다.

3. 동적 프로그래밍 배열 초기화

   • memo 배열은 각 작업까지의 최대 이익을 저장합니다. memo[i]는 i번째 작업까지 선택했을 때의 최대 이익을 의미합니다.

4. 최대 이익 계산

   • 각 작업을 순회하면서, 해당 작업을 선택했을 때와 선택하지 않았을 때의 최대 이익을 비교합니다.
   • 선택할 경우, 해당 작업 이전에 끝나는 작업들 중에서 가장 큰 이익을 더하여 계산합니다.
   • 이 과정을 통해, 현재 작업까지의 최대 이익을 memo 배열에 저장합니다.

5. 결과 반환

   • 최종적으로, memo[n]에 저장된 값이 주어진 작업들에서 얻을 수 있는 최대 이익입니다.

예제 설명

예를 들어, 주어진 작업이 다음과 같다고 가정합니다:

• 시작 시간: [1, 1, 1]
• 종료 시간: [2, 3, 4]
• 이익: [5, 6, 4]

이 경우, 종료 시간 기준으로 작업을 정렬하면 [1, 2, 5], [1, 3, 6], [1, 4, 4]가 됩니다.

동적 프로그래밍을 통해 각 작업까지의 최대 이익을 계산하면, 결과적으로 얻을 수 있는 최대 이익은 6이 됩니다.