딴딴딴~~ 오늘은 12월 16일입니다.
눈이 내리고 있었는데 지금은 그쳤다.
그러나... 나의 1일 1 블로그는 그칠 생각이 없다!!
오늘의 문제!!
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
으흠... 일단 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
이 분은 현재 회의를 초기화해주는 과정에서 순서가 조금 다르길래 참고하려고 한다.
알고리즘을 공부하다보면 이 문제가 어떻게 해야 풀리는지 도저히 모를 때가 많다...
그럴 때마다 잘 익히고 머리에 입력해 놔야 될 것 같다.
아자아자 파이팅~~~ 힘내자!!
'백준 > C++' 카테고리의 다른 글
[C++] 백준 1946번 신입 사원 (2) | 2023.12.18 |
---|---|
[C++] 백준 2587번 대표값2 (2) | 2023.12.17 |
[C++] 백준 2309번 일곱 난쟁이 (4) | 2023.12.15 |
[C++] 백준 1920번 수 찾기 (0) | 2023.12.14 |
[C++] 백준 11399번 ATM (2) | 2023.12.13 |