BOJ1931 회의실 배정

사용언어

C++

문제

입력

 

출력

---

예제 입력 1

 

---

예제 출력 1

---

문제 풀이

이 문제는 그리디를 이용해 풀었습니다. 

그리디는 현재의 값만을 통해 선택을 하는 방식입니다. 

편하지만 그렇기 때문에 그 값이 최적의 값인지 항상 증명을 해주어야합니다. 

 

다음과 같은 생각을 할 수 있을 겁니다. 

 

1. 빨리 시작하는 걸 기준으로 선택하자?

 

조금만 생각해봐도 안되는 걸 알 수 있습니다. 

 

2. 빨리 끝나는 걸 기준으로 선택하자?

이런식으로 빨리 끝나는 걸 선택해주면 조각조각이 나있는 회의들을 선택할 수 있습니다. 

그리고 다음 회의의 시작시간이 현재 진행중인 회의의 끝나는 시간보다 빠른지를 체크해주면 문제를 풀 수 있습니다.

 

코드를 다음과 같습니다.  

 

 

알고리즘 분류

그리디알고리즘 

 

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

1931번: 회의실배정