[백준]_1931번 : 회의실 배정(파이썬 and C언어)

 

1931번: 회의실 배정

가장 많은 회의 수를 배정하게끔 코드를 짜야한다. 그렇다면 어떤 접근을 해야 할까? 

 

먼저 문제를 푸는 데에 있어서 중요한 값들은 무엇이 있을까. 일단 회의실 배정을 많이 해야 되기 때문에 회의의 시작 시간과 마침 시간이 최대한 적어야 한다. 또한 직전에 끝난 회의 시간과 그다음에 시작할 회의의 시간 차이가 적어야 한다. 하지만 어느 것이 가장 중요하다고 할 수 있는가? 그렇지 않다. 바로 동시에 동등히 중요하다는 것이다. 

 

예제와 같은 답이((1,4), (5,7), (8,11), (12,14)) 어떻게 나오게 되었는지 생각해보자.

 

(1,4)는 존재하는 모든 타임테이블 중에서 가장 빨리 시작하지는 않지만((0,6) 때문에) 가장 빨리 종료된다. 그리고 (5,7)은 직전에 종료된 시간인 4 보다 크거나 같으면서 최대한 빨리 끝난다. 결국 중요한 것은 어떤 타임 테이블이 가장 빨리 끝나냐는 것이다. 따라서 아래와 같은 조건들을 우선순위를 두고 고려해 주어야 한다.

 

1. 가장 빨리 끝나는 회의

2. 직전 종료 회의 시간과 가장 가까운  

 

이제 타임 테이블을 전부 2차원 배열로 옮기고 나서 정렬을 진행해 주는 일만 남았다. 그렇다면 끝나는 시간이 정렬 1순위니까 배열의 인덱스 0에 대입해 주고 시작 시간을 인덱스 1에 할당해 주고 정렬을 시행해 주자.

 

시도 1(Python)

import sys
input = sys.stdin.readline
n=int(input())
ls=[]
for _ in range(n):
    s,f=map(int, input().split())
    ls.append([f,s])

cnt=1
ls.sort()
fin=ls[0][0]
for idx in range(1,n):
    if ls[idx][1]>=fin:
        cnt+=1
        fin=ls[idx][0]
print(cnt)

---

C언어로 짜도 별 다를 바는 없다. 다만 정렬 알고리즘을 스스로 만들어야 된다는 것이 귀찮을 뿐이다.

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    const int *rowA = *(const int **)a;
    const int *rowB = *(const int **)b;

    for (int i = 0; i < 2; i++) { 
        if (rowA[i] != rowB[i]) {
            return rowA[i] - rowB[i];
        }
    }
    return 0;
}

int main() {
    int n;
    int s,f;
    scanf("%d",&n);
    int **arr=(int **) malloc(n*sizeof (int *));
    for (int i = 0; i < n; ++i) {
        arr[i]=(int*)malloc(2*sizeof (int ));
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d %d",&s,&f);
        arr[i][0]=f;
        arr[i][1]=s;
    }

    int *rowPointers[n];
    for (int i = 0; i < n; i++) {
        rowPointers[i] = arr[i];
    }

    qsort(rowPointers, n, sizeof(int *), compare);

    int cnt=1;
    int fin=rowPointers[0][0];
    for (int i = 1; i < n; ++i) {
        if(rowPointers[i][1]>=fin){
            cnt+=1;
            fin=rowPointers[i][0];
        }
    }
    printf("%d",cnt);
    return 0;
}