[문제해결기법 2주차] Game

 

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

1931번: 회의실배정

https://kim6394.tistory.com/67

[백준 1931] 회의실 배정

-> 해당 문제 참고해서 풀수 있다.

 

 

-> 일종의 Greedy algorithm 문제로, 매 순간 최선의 방법을 찾는 것이 포인트인듯 하다.

-> 회의가 일찍 종료되는 순서대로 정렬을 해야 가장 최적의 방법을 찾을 수 있다!

 

//Greedy Algorithm!!

#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
//struct 구조체를 벡터와 결합시킬수 있다.
struct Time {
	int begin;
	int end;
 };

//일찍 끝나는 회의를 기준으로 잡으면 가장 최적의 경우를 구할 수 있다.

bool cmp(Time f, Time s) {
	if (f.end == s.end) { //종료 시간이 같다면, 시작 시간이 빠른 순
		return f.begin < s.begin;
	}
	else
		return f.end < s.end;
}//sort 함수에 정렬하는 기준도 집어넣을 수가 있다.

int main() {
	

	int testcase;
	int itemnum;

	cin >> testcase;
	while (testcase--) {
		cin >> itemnum;
		vector<Time>greedy(itemnum);
 //구조체와 결합시킬시 반드시 벡터 크기를 동적할당 해줘야 한다!!아니면 오류남
	     for(int i=0;i<itemnum;i++){
			 string name;
			 cin >> name;
			 cin >> greedy[i].begin >> greedy[i].end;
		}

		 sort(greedy.begin(), greedy.end(), cmp);



		 int cnt = 0;//가능한 개발 수
		 int n = 0;//회의 종료시점

		 for (int i = 0; i < greedy.size(); i++) {
			 if (n <= greedy[i].begin)
             //회의 종료 지점이 다음회의 시작 지점보다 빠르거나 같다면 바로 다음 회의 선택.
			 {
				 n = greedy[i].end;
				 cnt++;
			 }
		 }
		 cout << cnt << endl;
		 greedy.clear();
	}
	
}

 

 

+)vector subscript outof range가 자꾸 발생하는데, 이 포스팅 참고하장

https://m.blog.naver.com/PostView.nhn?blogId=nt0083&logNo=20086308967&proxyReferer=https%3A%2F%2Fwww.google.com%2F

[★★★★★]벡터 STL