BOJ_19621 : 회의실 배정 2

👉 문제링크

19621번: 회의실 배정 2

---

---

🔸 문제 분석 🔸

• 회의 시간에 진행할 수 있는 회의를 조절해, 회의에 참여한 인원의 최대값을 출력한다.
• 회의 별 최대 참여 인원을 DP에 저장하는 방식으로 풀이할 수 있다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(meetings);

        int[] dp = new int[n];
        int max = meetings[0].people;

        dp[0] = meetings[0].people;

        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (meetings[i].start > meetings[j].end && dp[i] < dp[j]) {
                    dp[i] = dp[j];
                }
            }
            dp[i] += meetings[i].people;
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }

    private static class Meeting implements Comparable<Meeting>{
        int start, end, people;

        public Meeting(int start, int end, int people) {
            this.start = start;
            this.end = end;
            this.people = people;
        }

        @Override
        public int compareTo(Meeting o) {
            return this.end - o.end;
        }
    }
}

🔸 코드 해석 🔸

• 회의를 종료 시간 순으로 오름차순 정렬한다.
• dp 배열을 순회하며 값을 채운다.
  • 인덱스에 해당하는 한 회의를 진행했을때, 회의 인원 합의 최대값을 저장한다.
    • 이전에 회의 중 연속으로 진행할 수 있는 회의의 참여 인원 최대값을 가져온다.
    • 갖고 온 참여 인원 최대값에 현재 회의의 참여 인원을 더해 저장한다.
  • 최대값과 비교해 업데이트한다.
• 최대값을 출력한다.

---

🔸 end 🔸

• 풀이를 다시보니 DP가 맞나 싶다. 브루트 포스로 풀이한 것 같다.
  • 다른 풀이를 찾아보니 DFS 등으로 풀이할 수 있는데, DP는 다른 풀이가 맞다.
  • 문제 제한에 앞 뒤로 인접한 회의만 시작,끝이 겹친다고 했으므로,
    점화식은 dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]) 가 된다.