문제

[백준] 회의실 배정

접근

끝시간이 중요하다

끝나는 시간을 최대한 당기면 더 많은 회의가능

1. end를 기준으로 vector pair를 만듬
2. vector 오름차순 정렬
3. 들어갈 수 있는 시작을 가진 회의 중 꼬리가 짧은 친구를 고른다

어려웠던 부분

• 여러 경우의 수 중에 무엇이 나은 지 잘 파악이 되지 않았다
  시작, 끝 두가지 경우가 변수로 주어지니 생각이 막혔다
  문제를 단순하게 보고 논리적으로 접근해봐야겠다
• 바킹독님의 강의에서 귀류법을 들었다
• 논리학들을 보면 이런 문제를 푸는데 도움이 될 수도 있겠다

귀류법

해결

# include <iostream>
# include <algorithm>
# include <vector>
using namespace std;

// 그리디의 어려운 점은 생각한 가정이 맞는 것인지 잘 판단이 서지 않는다는 것이다
// 이때는 귀류법?을 통해 찾아야 할 것 같다
// 이 방법을 습관적으로 써봐야겠다 -> 논리공부

int main() {
	int N, start, end;
	vector<pair<int, int>> meetings;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> start >> end;
		meetings.push_back(make_pair(end, start)); // end기준으로 정렬할 것
	}

	sort(meetings.begin(), meetings.end());		// end기준 정렬

	int time = meetings[0].first;		// 첫번째는 무조건 넣기
	int count = 1;						// end기준으로 정렬되어 있으니 뒷 공간 많아짐
	for (int i = 1; i < N; i++)
	{
		if (meetings[i].second >= time) { // 시작시간이 그전 end시간보다 크다면 통과
			time = meetings[i].first;	  // end 기준으로 정렬되어 있으니 가장 작은크기 회의가 들어옴
			count++;					  // end 시간 업데이트, 회의수 업데이트
		}
	}
	cout << count;
}

참고블로그
감사합니다!