[풀이]
정답 비율을 보고 쫄아있었는데.. 설마 이게 맞겠어 하며 제출했는데 바로 맞아버려서 생각보다 너무 간단하게 풀려 조금 허무했던 문제입니다.
책의 범위 a~b에서 b를 기준으로 우선 오름차순 정렬 하면, 어짜피 최고로 빌릴수 있는 숫자는 b까지 입니다.
그래서 a가 무슨 숫자가 오든 상관 없이 순서대로 주면 꼬일 일이 없습니다.
하지만 a를 기준으로 정렬한다면 최고로 빌릴 수 있는 숫자가 뒤죽박죽이 되면서 꼬여버리게 됩니다.
아래의 예를 봅시다
1 5 2 2
1 5 3 3
1 5 vs 1 5
2 2 1 5
3 3 1 5
(a 기준) (b 기준)
a를 기준으로 정렬했다면 1, 2, 3번 책밖에 주지를 못합니다.
하지만 반대로 b를 기준으로 했다면 2, 3, 1, 4, 5 순서로 모든 책을 빌려줄수 있겠죠??
자, 풀이를 정리해보자면,
1. 먼저 ai, bi쌍을 pair로 묶어 입력 받습니다.
2. pair의 second를 기준으로 오름차순, 그다음 first를 기준으로 오름차순 정렬을 해줍니다.
3. pair 배열을 순차적으로 돌면서 해당 범위 안에 있는 책을 줍니다.(이미 준 책은 제외)
예를 들자면
1 4 1 3
2 3 2 3
1 3 => 3 3
1 5 1 4
3 3 1 5
위처럼 입력받은 pair 쌍들을 second, first 기준으로 오름차순 해줍니다.
다음 처음 pair부터 돌면서 boolean 배열을 하나 두어 이미 준책은 true로 기록해둡니다.
아래는 풀이한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <algorithm>
using namespace std;
// second를 기준으로 우선 정렬하고 같을 경우 first를 기준으로 오름차순!
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.second < b.second) return true;
else {
if (a.second == b.second) {
if (a.first < b.first)
return true;
}
return false;
}
}
int main(void) {
int t;
cin >> t;
while (t-- > 0) {
int n, m;
cin >> n >> m;
pair<int, int> student[1000];
bool chosen[1000] = { false };
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
student[i] = make_pair(a, b);
}
sort(student, student + m, cmp);
int max_cnt = 0;
// 배열을 순차적으로 돌면서 해당 범위의 책 중 안 빌려준 책을 true로!!
for (int i = 0; i < m; i++) {
for (int j = student[i].first; j <= student[i].second; j++) {
if (!chosen[j]) {
chosen[j] = true;
max_cnt++;
break;
}
}
}
cout << max_cnt << endl;
}
return 0;
}
|
cs |
질문이나 지적사항은 댓글 부탁드립니다 :)