1931번 회의실 배정 BOJ 백준 C언어

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

구현

제일 중요한 점은 첫 번째로 쓸 회의실이 끝나는 시간이 가장 짧은 것을 구해야 한다는 것을 파악하는 점이다. 첫 번째로 쓸 회의실이 끝나는 시간이 가장 짧은 것을 구했다면 그 이후로는 그리디 알고리즘에 맞게 다음으로 짧은 것들을 구해가면 된다. 입력받은 두개의 시간을 배열에 넣어서 끝나는 시간을 오름차순으로 정렬한 후 끝나는 시간과 배열의 시작하는 시간을 비교해가며 cnt를 더해주며 구현한다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

struct arr {
    int x;
    int y;
};

arr array[100000];

bool compare(arr const &a, arr const &b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

int main(void) {
    int i = 0, num = 0, x, y, cnt = 0, cur = 0;
    scanf("%d", &num);

    for (i = 0; i < num; i++) {
        scanf("%d", &x);
        scanf("%d", &y);
        array[i] = { x,y };
    }

    std::sort(array, array + num, compare);

    for (i = 0; i < num; i++) {
        if (i == 0) {
            cnt++;
            cur = array[i].y;
        }
        else {
            if (array[i].x >= cur) {
                cnt++;
                cur = array[i].y;
            }
        }
    }
    printf("%d", cnt);
}

정리

그리디 알고리즘의 가장 기초는 동적 프로그래밍과는 다르게 바로 앞에 보이는 가장 좋은 것을 구하는 것이다. 두가지 모두 수학적?으로 비슷한 면이 있어 보이지만 동적 프로그래밍은 다양한 경우의 수 중에서 최선의 방법을 찾아내는 알고리즘이고 그리디 알고리즘은 다양한 경우의 수 중에서 현재 할 수 있는 최선의 방법을 찾아내는 알고리즘이라는 다른 점이 있다.