(백준 1931번 회의실 배정 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 6탄

진짜 그리디😥... 알고리즘.. 애증의 알고리즘이다. 오늘의 그리디 문제는 바로 회의실 배정 문제!!

 

이전 포스팅은 여기에!↓

2024.01.04 - [알고리즘] - (백준 4796번 캠핑 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 5탄

(백준 4796번 캠핑 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 5

 

백준1931번

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

1931번: 회의실 배정

 

처음에 짤 때는 꽤나 쉽다고 생각했는데 시간초과로 터져버렸다..🥶

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector> // vector 사용 
#include <algorithm> // sort사용
bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b);

int main() {
	int N; scanf("%d", &N);

	std::pair<int, int> p[100000];
	for (int i = 0; i < N; i++) scanf("%d %d", &p[i].first, &p[i].second);

	sort(p, p + N, compare);// compare이 없다면 first값을 기준으로 오름차순, first값이 같으면 second값을 기준으로 오름차순

	int cnt = 1, Tend = 0, idx =0;
	while (1) {
		if (idx > N - 1) break;
		Tend = p[idx].second;
		while (1) {
			if (idx > N - 1) break;
			if (p[idx].first >= Tend) {
				cnt++;
				break;
			}
			else idx++;
		}
	}

	printf("%d", cnt);

}
bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b) {
	if(a.second == b.second){
		return a.first > b.first; //더 큰게 앞으로(내림차순) (회의가 늦게 시작하는 걸 앞에 배치)
	}
	return a.second < b.second; // 더 큰게 뒤로(오름차순) (회의가 늦게 끝나는걸 뒤로 배치)
}

 

처음에는 sort를 pair에 써서 터진 줄 알았는데 알고보니 잘못된 부분은 다른 곳이었따..🥲

https://jjo-mathstory.tistory.com/entry/%EB%B0%B1%EC%A4%80-13904%EB%B2%88-%EA%B3%BC%EC%A0%9C-C-%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-3-%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm-2%ED%83%84

(백준 13904번 과제 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 2

 

일단 이런 식으로 디버깅에 다 매달리기에는 내 실력도 부족하고, 시간도 부족해서 살짝 집단 지성의 힘을 빌려봤따. 

(말 할 수는 없지만 이 알고리즘을 올해 끝짱내야할 이유가 있따!!!)

 

https://cocoon1787.tistory.com/147

[C/C++] 백준 1931번 - 회의실 배정 (그리디 알고리즘)

나랑 풀이가 거의 같으셨지만.. 다른 점은..

1. sort가 첫번째 원소 기준으로 이루어진다는 것을 이용해 입력을 반대로 받은 것

2. while loop대신 for loop을 사용한 것

3. 그리고,,,, !!!에서 달랐다

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm> // sort사용
#include <vector>
bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b);
int main() {
	int N; scanf("%d", &N); int temp1; int temp2;
	std::vector<std::pair<int, int>> p;
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &temp1, &temp2);
		p.push_back(std::make_pair(temp2, temp1));
	}

	std::sort(p.begin(), p.end());// first값을 기준으로 오름차순;

	int cnt = 1, idx = 0; int Tend;
	Tend = p[0].first; // 첫번째 회의의 종료시간
	for (int i = 1; i < N; i++) { //!!!!!!!!!!!!!!!!!!!!!!
		if (p[i].second >= Tend) {
			cnt++;
			Tend = p[i].first;
		}
	}
	printf("%d", cnt);

}

나는 별 생각 없이 for loop을 i = 0부터 실행했는데 이렇게 되면 시작시간 = 종료시간인 회의가 무한번 카운트된다.

즉, 이런 경우 시간초과가 발생할 수 있다는 의미다!!!!

 

나는 이 점을 간과하고 코드를 작성했었는데, 처음에 시간초과가 발생했을 때는 sort함수의 이상인 줄 알았따.

흙흙 그리디 진짜 정복하고 싶따!!!!!!

갸갸갸갸갸갸갸갸갹

갸갸갸갸갸갸갸갸갸갸