백준 1931번 - 회의실 배정

구현 방법

풀이 방법은 여러 가지가 있을 수 있다.

1. 절차적인 방법: 해당 회의실을 선택할지 말지로 나뉘어 총 O(2^N) 시간복잡도가 걸린다.
2. dp(귀납법, 점화식):
   • dp 배열을 결정한다.
     • 값: 사용할 수 있는 회의의 최대 개수
     • 기준(인덱스): 시간 혹은 회의 index => 시간 자체가 굉장히 큰 값을 가지기 때문에 적절치 않다.
       회의를 기준으로 사용한다. 회의를 그냥 사용하는 것이 아닌 정렬하여 사용하여 된다.
   • 점화식을 세운다.
     • 정렬한 회의 리스트에 대해서 K 번째 회의까지 고려했을 때 사용할 수 있는 회의의 최대 개수는
       K - 1 번째까지 고려했을 때 선택되는 마지막 회의의 end <= K번째 회의.start dp[K] = dp[K - 1] + 1
     • 만약 첫번째 경우가 아니라면 선택된 마지막 회의의 end <=  가 K번째 회의.start 인 인덱스를 찾고 해당 인덱스를 X 라고 하면 dp[K- 1] 와 dp[X] + 1를 비교하여 큰 값을 선택한다.
   • dp 로 풀었을 때 시간 복잡도가 O(N^2)이기 때문에 풀이 시간안에 못 들어온다.
3. 그리디 알고리즘
   • 회의 리스트 정렬
   • for 문을 돌며 회의를 선택한다. 이 때 이전에 선택된 회의의 end를 저장한 limit 보다 현재의 회의의 start 를 비교하여 같거나 현재 회의의 start 가 크다면 선택하고 limit 를 현재 회의의 end 로 갱신한다.

코드

dp를 이용한 풀이

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

public class Main{
    private static int N;
    private static Meeting[] meetings;
    private static int[] dp;
    private static int[] lastMeetings;

    public static void main(String[] args) throws IOException {
        readInput();
        solve();
    }

    private static void readInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        meetings = new Meeting[N];
        dp = new int[N + 1];
        lastMeetings = new int[N + 1];

        for(int i = 0; i < N; i++){
            String[] meetingInfos = br.readLine().split(" ");
            meetings[i] = new Meeting(Integer.parseInt(meetingInfos[0]), Integer.parseInt(meetingInfos[1]));
        }
    }

    private static void solve(){
        // end 기준 오름차순 정렬
        Arrays.sort(meetings, (a, b) -> {
            if(a.end == b.end){
                return a.start - b.start;
            }
            return a.end - b.end;
        });

        // 초기화
        dp[0] = 1;
        lastMeetings[0] = 0;

        for(int i = 1; i < N; i++){
            if(meetings[lastMeetings[i - 1]].end <= meetings[i].start){
                dp[i] = dp[i - 1] + 1;
                lastMeetings[i] = i;
            }
            else{
                int j;
                for(j = i - 1; j >= 0; j--){
                    if(meetings[lastMeetings[j]].end <= meetings[i].start) break;
                }
                if(j == -1 || dp[i - 1] >= dp[j] + 1){
                    dp[i] = dp[i - 1];
                    lastMeetings[i] = lastMeetings[i - 1];
                }
                else{
                    dp[i] = dp[j] + 1;
                    lastMeetings[i] = i;
                }
            }
        }
        System.out.println(dp[N - 1]);
    }

    private static class Meeting{
        int start;
        int end;

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

 

그리드를 이용한 풀이

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

public class Main{
    private static int N;
    private static Meeting[] meetings;

    public static void main(String[] args) throws IOException {
        readInput();
        solve2();
    }

    private static void readInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        meetings = new Meeting[N];

        for(int i = 0; i < N; i++){
            String[] meetingInfos = br.readLine().split(" ");
            meetings[i] = new Meeting(Integer.parseInt(meetingInfos[0]), Integer.parseInt(meetingInfos[1]));
        }
    }

    private static void solve2(){
        Arrays.sort(meetings, (a, b) -> {
            if(a.end == b.end) return a.start - b.start;
            return a.end - b.end;
        });

        int end = 0;
        int result = 0;

        for(int i = 0; i < meetings.length; i++){
            if(meetings[i].start >= end){
                end = meetings[i].end;
                result++;
            } 
        }

        System.out.println(result);
    }

    private static class Meeting{
        int start;
        int end;

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

 

결과