교훈
뭔가 애매하지만 영향이 없을 것 같아서 넘어갈 때는, 반드시 각주로 기록하고 넘어가자!
- Baekjoon 문제 링크
- BOJ 홈페이지 > 문제 > 알고리즘 분류 > 그리디 알고리즘
- 나동빈님이 이 영상에서 1단계로 그리디 알고리즘을 풀라고 하시길래 한번 풀어봤습니다!
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
-
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다. -
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14예제 출력 1
4- 힌트
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
발상
Solution #1
일단, 이게 그리디인 걸 알고 갔어서 그나마 접근했지 그리디로 분류된 줄도 몰랐다면 그냥 헤매다가 끝났을 것이다.
그리디라길래 그래도 동전 문제처럼 뭔지 모를 기준으로 정렬해서 앞에서부터 되는대로 채우다보면 최댓값이 나오겠지 확신은 가졌다.
첫번째는 시작시간 빠른 순으로 해보았다.
반례가 바로 나온다.
5
1 100
2 3
4 5
5 6
6 7시작시간 빠른 순으로 고른다면, 1 100 하나만 고르고 끝낼 것이기에 1을 출력할 것이다.
하지만 우리는 직관적으로 안다.
1 100만 안 고르면 2 3 4 5 5 6 6 7 4개를 다 고를 수 있다는 사실을.
Solution #2
그다음 생각난 건 회의 시간(끝나는 시간 - 시작 시간)이 작은 순이었다.
이건 그래도 앞에 것보다는 솔깃했다.
그런데 조금만 더 생각해보니 반례가 나왔다.
3
5 7
0 6
6 105 7이 회의 시간은 2로 가장 작기 때문에 5 7을 먼저 선택하고, 나머지 두개는 모두 5 7과 시간이 겹치기 때문에 1을 출력할 것이다.
하지만 실제로는 0 6과 6 10을 선택하는 것도 가능하며, 답은 2다.
Solution #3
사실 이 해결책은 직관적으로 떠오르지 않았다.
그런데 남은 정렬 기준이 이것밖에 없어서 해볼 수밖에 없었다...
바로 끝나는 시간 빠른 순이다.
그때는 왜 되는지 몰랐지만, 답이 나오니까 신기했다.
N = int(input())
arr = []
for _ in range(N):
arr.append(list(map(int, input().split())))
# 많이 고민했지만, 끝나는 시간을 기준으로 오름차순 정렬해서 그리디 하는게 포인트
arr.sort(key=lambda x: x[1])
cnt = 0
latest_end = 0
for start, end in arr:
if latest_end <= start:
cnt += 1
latest_end = end
print(cnt)근데 100% 가까이 가서 틀렸습니다가 나오는 게 아닌가?
맞왜틀...
끝나는 시간으로만 정렬하면, 끝나는 시간이 같을 때 문제가 생기나?
[1, 3], [4, 5], [3, 5] 여기에 [3, 4]를 넣어도 에러 안 생기잖아...반례를 찾으려고 노력했지만, 찾을 수 없었다.
그리고 정렬하면서, 만약 끝나는 시간이 같으면 다음 정렬 기준은 어떡하지? 라는 생각을 하긴 했지만, 별 문제가 되지 않을 것 같아 넘긴 기억이 한 편에 남아 있었다.
https://hongcoding.tistory.com/22
를 보고서야 반례가 있음을 깨달았다.
3
1 9
10 10
9 10정렬 기준은 끝나는 시간 빠른 순이므로, 10 10 9 10은 순서를 유지한다.
따라서 1 9 다음 10 10을 고르고,
최근 회의가 끝난 시간인 10보다 빠른 타임에 있는 9 10은 배제된다.
하지만 1 9 9 10 10 10 순으로 고르면, 3개를 다 고를 수 있다.
핵심은 10 10이라는 엣지 케이스에 있었다.
회의를 시작하자마자 끝내버리는 게 무슨 회의인진 모르겠다만...추가적으로 위 링크에서는, 끝나는 시간 빠른 순으로 했을 때 왜 답이 나오는지에 대한 발상도 알려준다.
그리디는 당장의 상황을 기준으로 확장시키는 방향으로 풀면 쉽게 해결이 가능한 경우가 많다.
내가 회의실을 사용하고 있다고 가정했을 때, 내 회의가 끝난 후에 회의실에서 가장 많은 회의가 열리기 위해서는 어떤 상황이 되야할까? 바로. 내 회의가 빨리 끝나야 하는 것이다. 즉, 종료 시간이 빨라야 한다.
풀이
N = int(input())
arr = []
for _ in range(N):
arr.append(list(map(int, input().split())))
# 많이 고민했지만, 끝나는 시간을 기준으로 오름차순 정렬해서 그리디 하는게 포인트
arr.sort(key=lambda x: (x[1], x[0])) # tuple을 key로 하면 앞 요소부터 1순위, 2순위로 자동으로 간주해준다.
cnt = 0
latest_end = 0
for start, end in arr:
if latest_end <= start:
cnt += 1
latest_end = end
print(cnt)