회의실 배정 - 백준 BOJ 1931 + 증명

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

---

접근법 및 풀이

이제 입력크기를 통해 시간초과를 따지는 과정이 자연스럽게 이루어지는 것 같다 v

완전탐색은 당연히 시간초과가 날 것 이고, 최적화를 진행한다면 dp 인가 싶기도 했지만, 문제의 조건 때문에 모든 케이스에 대해서 상위 문제가 하위 문제를 포함하지 못하므로 dp 도 아니었다.

 

회의실을 고르는 작업이 시간순서에 따라 제약을 받으므로, 우선 정렬을 수행해야할 것 같은 느낌이 들었고,

이내 예전에 비슷한 문제를 학교수업 때 들은 기억이 났고, 정렬을 통한 그리디 문제였음이 떠올랐다

 

그리디 하게 회의실을 선택하는 과정은 다음 고를 회의의 시작지점이, 이전에 선택한 회의의 종료시점보다 크거나 같으면 될 것 이다

 

int[] joinedMeeting = sortedTimeLines[0];	// 특정 기준으로 정렬된 회의들
int count = 1;
int index = 1;

while(index < meetingCount) {
    int[] currMeeting = sortedTimeLines[index];
    int currMeetingStartTime = currMeeting[0];
    int joinedMeetingEndTime = joinedMeeting[1];

    if(joinedMeetingEndTime <= currMeetingStartTime) {
        System.out.println("Choose " + currMeeting[0] + ", " + currMeeting[1]);
        joinedMeeting = currMeeting;
        count++;
    }

    index++;
}

 

 

 

이제 문제는 어떤 것을 기준으로 정렬하냐가 남아있다

 

1차원적으로 접근해보면, 회의가 빨리 시작하는 순으로 정렬하면 그만큼 많이 고를 수 있지 않을까? 하는 생각이 든다

회의의 시작순으로 정렬해보자

 

 

첫 회의를 시작으로, 그리디하게 회의실을 선택해보자. 그럼 선택된 회의는 [0, 6], [8, 11], [12, 14] 가 된다

 

주황색이 선택된 회의

 

하지만 선택된 결과보다 더 최적인 결과가 있을 것 같다, 처음 고른 회의인 [0, 6] 이 그 이유인데,

만약에 첫 회의가 0시에 시작해서 100,000 시에 끝나버린다면?  이는 절대 최적의 선택이 아니다.

 

그렇다면, 정렬된 회의 중 첫번째 회의를 참가하지 말고, 두번째 회의부터 참가한다면?

비슷한 문제는 계속 발생할 수 있으므로, 결국에 n 번째 회의가 아닌 n + 1 번째 회의부터 참가한다라는 상황이 반복되므로 이때는 시간복잡도에서 걸려버린다 ( O(N ^ 2) )

 

즉, 회의의 시작순으로 정렬을 수행했을 때, 기존의 그리디 방법으로는 최적의 해가 나오지 않는다.

다른 방법을 찾아야 하는데, 우리는 기존의 정렬조건에서 발생했던 문제점인, 첫 회의가 0시에 시작해서 100,000 시에 끝나버린다면? 에 집중할 필요가 있다.

최대한 많은 회의를 선택하는 과정에서 시작시간이 아닌 끝나는 시간에 더 제약을 받는 것 같다는 느낌이 든다, 따라서 시작 시간이 아닌 끝나는 시간을 기준으로 정렬을 수행해보자

 

 

주황색이 현재 정렬조건에서의 그리디한 선택이다

 

 

위의 그림과 같이 주어진 조건에서 최대 회의실을 선택했을 때 최적의 해가 나옴을 확인할 수 있다.

 

 

한가지 주의할 점이라면

 

 

이러한 조건 때문에 종료순으로 정렬하는데 있어서 같은 숫자가 주어질 수 있다

만약 종료시점이 같은 타임라인에 대해서 정렬조건을 설정해주지 않으면

 

2
2 2
1 2

// 답은 2인데 1이 나옴

 

위 케이스와 같은 엣지케이스가 존재하므로

종료시점이 같을경우, 시작지점의 오름차순으로 정렬하는 조건을 넣어주자

찾아내기 힘든 케이스여서.. 나는 맞왜틀 하다가 다른사람 풀이를 봤다 ㅠㅠ

---

증명

근데 정말 끝나는 시간의 오름차순으로 정렬해서 그리디하게 고른게, 최적의 해가 되나?

그리디는 이게 어려운 것 같다. 뭔가 그럴 것~ 같은데, 막상 이게 정말 맞는지는 모르겠고...

결국 Proof of AC ( 코드 제출해서 통과함으로서 증명 ) 로 확인을 해야하는데, 실전 코딩테스트 에서는 그런거 없다

 

Proof of AC 가 아닌 귀납적 증명을 통해 해당 가설을 증명해보자

 

우선 Base Condition 인 n = 1 일 때를 보자

타임라인이 하나일 경우 정렬이 필요 없이 결과값은 항상 같다. 고로 n = 1 일때는 참

 

이제 1보다 큰 k 에 대해서 살펴보자

 

 

만약 종료시간으로 정렬한 최적의 해가 아닌 다른 최적해를 도출할 수 있는 회의시간의 정렬조건이 존재한다고 해보자

k 까지는 두 조건 모두 동일한 회의시간을 선택했을 때

다음 회의시간을 선택하는데 있어서, 존재할 수 있는 다른 최적의 정렬조건에 의해 기존의 정렬과는 다른 타임라인이 선택될 것 이다.

이 때 기존의 정렬조건에서 선택된 타임라인을 Greedy, 존재할 수도 있는 최적의 해에서 선택된 타임라인을 Might Optimal 이라고 하자

 

종료시점의 오름차순이 아닌 다른 조건으로 정렬된 타임라인 중 선택된 Might Optimal 은 Greedy 보다 종료 시점이 밀려있는 것은 자명한 사실이다

 

Might Optimal 이 밀려있는 시간의 길이를 d 라 하자

 

 

따라서 타임라인을 선택하는데 있어서 기존의 정렬 조건은 존재할수도 있는 최적 해보다 d 만큼의 시간을 더 가져갈 수 있는 것이다.

이 d 의 크기에 따라서 저 안에는 0 개 이상의 타임라인이 더 들어갈 수 있으므로 Might Optimal 은 최적이 선택이 아님, 즉 최적일 수 있는 다른 정렬 조건은 존재하지 않는다.

 

이렇게 해서 종료조건의 오름차순이 아닌 다른 조건으로 정렬된 타임라인 에서는 최적의 해가 나올 수 없음이 증명되었다

 

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int meetingCount = Integer.parseInt(br.readLine());

        int[][] timeLines = new int[meetingCount][2];

        for(int i = 0; i < meetingCount; i++) {
            timeLines[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int[][] sortedTimeLines = Arrays.stream(timeLines)
                .sorted((t0, t1) -> {
                    if(t0[1] == t1[1]) {
                        return t0[0] - t1[0];
                    }

                    return t0[1] - t1[1];
                })
                .toArray(int[][]::new);

        int[] joinedMeeting = sortedTimeLines[0];
        int count = 1;
        int index = 1;

        while(index < meetingCount) {
            int[] currMeeting = sortedTimeLines[index];
            int currMeetingStartTime = currMeeting[0];
            int joinedMeetingEndTime = joinedMeeting[1];

            if(joinedMeetingEndTime <= currMeetingStartTime) {
                joinedMeeting = currMeeting;
                count++;
            }

            index++;
        }

        System.out.println(count);
    }
}