[c++] 백준 1931 - 회의실배정(그리디 알고리즘, 정렬)

0. [c++] 백준  -

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

1. 풀이

아래의 풀이는 다음과 같다.

1. 끝나는 시간을 기준으로 오름차순 정렬을 한다.(sort를 활용하면, pair는 first를 먼저 오름차순으로 맞추고, first가 동일한 경우, second를 오름차순 해서 정렬해준다.)

2. 이후 회의가 최종적으로 끝난 시간을 int(whatTimeIsItNow)에 기억시키면서, 시작 시간이 이것과 같거나 더 큰 경우, 바로 다음 회의로 채용을 해주면 된다.

이것이 가능한 이유는, 끝나는 시간이 오름차순으로 정렬되어있기 때문이다.

가장 많은 회의를 집어넣기 위해서는 어떤 회의가 가장 빨리 끝나는지를 확인하고, 빨리 끝나는 회의를 우선적으로 넣어주는 것이다.

-----------------------------------------------------------------------------------------

실패한 방법

처음엔 vector에 집어넣는 순서를 {시작 시간, 끝난 시간} 순으로 집어넣었다.

이후 오름차순으로 정렬을 한 이후, 시작 시간이 겹치는 경우는 erase연산을 통해 배열의 길이를 줄여주었다.

마지막으로 이 경우를 선택한 경우와 선택하지 않는 경우로 나누어 메모이제이션과 동적 계획법을 적용하여 문제를 풀어보았는데, 이 경우는 시간 초과를 하게 되었다.

2. 소스코드

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

typedef unsigned long long ull;

vector<pair<int, int>> timeTable;

int N;

int dp() {

int ret = 0;

int whatTimeIsItNow = 0;

for (int i = 0; i < N; i++) {

if (timeTable[i].second >= whatTimeIsItNow) {

ret++;

whatTimeIsItNow = timeTable[i].first;

}

}

return ret;

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

cin >> N;

int a, b;

for (int i = 0; i < N; i++) {

cin >> a >> b;

timeTable.push_back({ b,a });

}

sort(timeTable.begin(), timeTable.end());

////중복되서 필요없는 수를 지워준다.

//for (int i = 1; i < N; i++) {

// while (i < N && timeTable[i - 1].first == timeTable[i].first) {

// timeTable.erase(timeTable.begin() + i);

// N--;

// }

//}

/*for (int i = 0; i < N; i++) {

cout << timeTable[i].first << " " << timeTable[i].second << endl;

}*/

cout << dp();

return 0;

}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!