-
(백준 1931번 회의실 배정 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 6탄PROGRAMMING/알고리즘 2024. 1. 4. 23:28
진짜 그리디😥... 알고리즘.. 애증의 알고리즘이다. 오늘의 그리디 문제는 바로 회의실 배정 문제!!
이전 포스팅은 여기에!↓
2024.01.04 - [알고리즘] - (백준 4796번 캠핑 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 5탄
(백준 4796번 캠핑 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 5
출근 5분전! 질문 게시판의 반례 도움을 받아 한문제 풀고 간다!(오늘은 진짜 하기 싫어서 질문게시판에서 반례 살짝 훔쳐봤습니다..🥲) 이전 포스팅은 여기에!↓ 2024.01.02 - [알고리즘] - (백준 221
jjo-mathstory.tistory.com
백준1931번
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
처음에 짤 때는 꽤나 쉽다고 생각했는데 시간초과로 터져버렸다..🥶
#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에 써서 터진 줄 알았는데 알고보니 잘못된 부분은 다른 곳이었따..🥲
(백준 13904번 과제 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 2
오늘은 과제가 많은 웅찬이가 좋은 학점을 받도록 도와주고자 한다.(문제 내용의 일부임, 웅찬이 모름) 요건 그리디 알고리즘 1탄!↓ 2023.12.29 - [알고리즘] - (백준 1969번 DNA C++) 라이님 블로그 대
jjo-mathstory.tistory.com
일단 이런 식으로 디버깅에 다 매달리기에는 내 실력도 부족하고, 시간도 부족해서 살짝 집단 지성의 힘을 빌려봤따.
(말 할 수는 없지만 이 알고리즘을 올해 끝짱내야할 이유가 있따!!!)
https://cocoon1787.tistory.com/147
[C/C++] 백준 1931번 - 회의실 배정 (그리디 알고리즘)
예제에서 주어진 입력을 시각화 하면 위와 같은 스케줄 표가 나온다. 문제에서 조건은 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기 회의는 한번 시작하면 중
cocoon1787.tistory.com
나랑 풀이가 거의 같으셨지만.. 다른 점은..
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함수의 이상인 줄 알았따.
흙흙 그리디 진짜 정복하고 싶따!!!!!!
갸갸갸갸갸갸갸갸갹 갸갸갸갸갸갸갸갸갸갸 'PROGRAMMING > 알고리즘' 카테고리의 다른 글