[백준] 11000번 문제풀이

문제 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 

나의 풀이방법(틀린방법) :

1. 강의 시작 시간(s)을 기준으로 오름차순 정렬을 함.

2. 앞에서 나온 강의 끝나는 시간(t) 보다 뒤에나온 s와 t에 따라서 count를 해주고 말고를 결정함.

3. count 출력.

 

#include <stdio.h>

struct LECTURE
{
    int s;
    int t;
} lecTime[200000];

struct LECTURE temp[200000];

void merge(int left, int mid, int right)
{
    int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) // i나, j가 index를 넘어갈 경우 while문에서 빠져나옴.
        {
            if (lecTime[i].s < lecTime[j].s) { temp[k++] = lecTime[i++]; } // i와 j를 비교해서, temp 배열에 작은순서대로 집어넣음.
            else { temp[k++] = lecTime[j++]; }
        }
        while (i <= mid) { temp[k++] = lecTime[i++]; }
        while (j <= right) { temp[k++] = lecTime[j++]; }
        for (int a = left; a <= right; a++) { lecTime[a] = temp[a]; }
        return;
}

void mergeSort(int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }
}

int main(void)
{
    int n, cnt = 1;
    scanf("%d", &n);

    
    for (int i = 0; i < 200000; i++) {
        lecTime[i].s = 0;
        lecTime[i].t = 0;
    }
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &lecTime[i].s, &lecTime[i].t);
    }
    
    mergeSort(0, n - 1);
    
    int maxT = lecTime[0].t;
    for (int i = 1; i < n; i++) {
        if(lecTime[i].s >= maxT) {
            cnt++;
            maxT = lecTime[i].t;
            continue;
        }
    }
    
    if(lecTime[n - 1].s < maxT && lecTime[n - 1].t > maxT)
    {
        cnt++;
    }
    
    printf("%d",cnt);
}

 

생각보다 어려운 문제를 너무 간단하게 풀려고만 했다. TC를 위주로 풀려고 했다.

어려운 문제인지 몰랐다. 문제 지문이 짧아서 쉽다고만 생각했나보다.. 나의 실수이다.

 

이 문제를 푼 사람의 소스코드를 분석해서 다시 한 번 풀어보아야겠다.