[C++] 백준 1931번 회의실 배정

 

딴딴딴~~ 오늘은 12월 16일입니다.

 

눈이 내리고 있었는데 지금은 그쳤다.

그러나... 나의 1일 1 블로그는 그칠 생각이 없다!!

 

오늘의 문제!!

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

1931번: 회의실 배정

 

 

 

으흠... 일단 pair로 입력받고 정렬을 한 후에 하나씩 회의실을 선택해 가며 최대로 사용할 수 있는 회의의 최대 개수를 알아내면 될 것 같다.

 

 

// 틀린 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int current_indx = 0;
int current_num;
int maxroom = 0;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	vector <pair<int, int>> room(n);
	for (int i = 0; i < n; i++) {
		cin >> room[i].first >> room[i].second;
	}
	sort(room.begin(), room.end());

	for (int i = 0; i < n-1; i++) {
		current_num = 0;
		if (current_num > maxroom) {
			maxroom = current_num;
		}
		current_indx = i;
		current_num++;
			
		for (int j = i + 1; j < n; j++) {
			if (room[i].second <= room[j].first) {
				i = j;
				current_num++;					
			}
		}
		i = current_indx;
	}

	cout << maxroom << "\n";

	
	return 0;
}

 

 

예제 문제도 못 풀었다...

어떻게 풀어야할지 모르겠어서 그냥 다른 풀이를 보고 내 코드를 고쳐보았다.

 

처음에는 무슨 소리인가 했는데 설명을 보니 시작하는 시간이 빨라도 늦게 끝나면 최대 회의의 수를 맞출 수 없다고 한다.

나는 하나하나 다 회의의 수를 count 해서 비교하려고 했는데 그럴 필요가 없었던 것이다..ㅎㅎ

 

그래서 vector에 입력을 받을 때 종료 시점을 first로 받아서 종료시점에 대해 정렬한 뒤 current에는 종료시간이 가장 빠른 종료시점으로 초기화한다. 그다음 시작 시점이 현재 종료시점보다 크거나 같은지 확인하여 그것을 current에 다음 회의 종료 시간으로 저장한다. 그렇게 count를 해주고 모든 시간을 확인할 때까지 반복해 준 후 count 한 것을 출력해 주면 되는 것이다. 

 

이렇게 다른 풀이를 찾아봐서 이해를 한 것이라서 나중에 한번 다시 풀어봐야할 것 같다...

[참고] https://cocoon1787.tistory.com/147

 

 

 

내 코드를 위와 같이 고치면

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	vector <pair<int, int>> room(n);
	for (int i = 0; i < n; i++) {
		cin >> room[i].second >> room[i].first;
	}
	sort(room.begin(), room.end());

	int current = room[0].first;
	int maxroom = 1;
	for (int i = 1; i < n; i++) {
		if (current <= room[i].second) {
			maxroom++;
			current=room[i].first;
		}
	}
	

	cout << maxroom << "\n";

	
	return 0;
}

 

 

 

 

다시 정리해보면 이 알고리즘은 끝나는 시간을 오름차순으로 정렬하고 시작 시간이 현재시간보다 크거나 같을 경우 그 회의를 다음 회의로 잡고 count 해주는 것이다. 여기서 중요한 점은 끝나는 시간을 중심으로 시간을 정렬하기 때문에 끝나는 시간을 앞에 오도록 입력받아야 한다는 것이다. 

 

 

 

 

 

다른 풀이는 어떤지 보는데 pair를 sort를 하면 첫 번째 인자를 오름차순 정렬하기 때문에 다른 사람들도 두 번째 값을 정렬하기 위해 second와 first 순서를 바꿔입력받았다. 

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N,connect,cnt;
 
 
int main() {
    // 반복횟수 입력 받기
    cin >> N;
 
    // 시간 쌍 입력 받는 pair선언
    vector<pair<int, int>> p(N);
 
    // pair 입력 받기
    for (int i = 0; i < N; i++)
    {
        // pair를 sort하면 첫 번째 인자를 오름차순 정렬해서 두 번째 값을 정렬하기 위해 second와 first순서를 바꿔 입력 받음
        cin >> p[i].second >> p[i].first;
    }
 
    // 끝나는시간을 오름차순으로 정렬
    sort(p.begin(), p.end());
 
 
    cout << endl;
 
    // 첫 번째 수가 connect(0으로 시작)q보다 크면 해당 케이스의 second를 connect에 담아서 갱신
    for (int i = 0; i < N; i++) {
        if (p[i].second >= connect) {
            connect = p[i].first;
            cnt++;
        }
    }
}
출처: https://perconsi.tistory.com/66

 

이 분은 현재 회의를 초기화해주는 과정에서 순서가 조금 다르길래 참고하려고 한다.

 

 

 

알고리즘을 공부하다보면 이 문제가 어떻게 해야 풀리는지 도저히 모를 때가 많다...

그럴 때마다 잘 익히고 머리에 입력해 놔야 될 것 같다.

 

아자아자 파이팅~~~ 힘내자!!