문제링크 : https://www.acmicpc.net/problem/1946
문제 접근
- 문제를 추상화 하면
- A와 B 과목에서 하나라도 다른 사람에 비해 떨어지면 안됨
- 모두 떨어지는 경우를 구하는게 쉬울듯
- 접근 1 : 각 노드당 모든 노드를 순회하면서 모두 떨어지는 경우를 구할경우
- O(N^2) > e10 시간초과
- 접근 2 : 하나를 기준으로 나머지 값의 최소값을 갱신
- A,B 과목이 있을때 A 과목을 기준으로 정렬
- A과목의 순위가 가장 높은 지원자의 B과목 순위를 최소값의 초기 셋팅
- A과목 순위가 낮은 것들을 순회
- A 과목 순위가 낮기 때문에, B과목은 더 순위가 높아야함
- B과목의 순위를 최소값으로 갱신하면서 순회
시간복잡도 계산
- 테스트케이스 : T
- A과목을 기준으로 정렬 : NlgN
- 모든 지원자 순회 : N
- 시간복잡도 : O(T * (NlgN + N)) = O(TNlgN) =20* 1e5 * 20 = 4e7
인트 계산
- 면접 지원자숫자 최대 1e6 > 인트 가능
코드
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> people[100010];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;cin >> T;
while(T--) {
int N; cin >> N;
for(int i=0; i<N; i++) {
int a,b; cin >> a >> b;
people[i] = make_pair(a,b);
}
sort(people, people+N);
int minv= people[0].second;
int cnt=0;
for(int i=1; i<N; i++) {
// A과목 순위가 높은 사람의 B과목 순위도 순위가 높다면 카운트
if(minv < people[i].second) {
cnt++;
}
// 최소 순위 갱신, 왜냐하면 다음 사람은 최대값과 비교
minv = min(minv, people[i].second);
}
cout << N-cnt << '\n';
}
return 0;
}
|
cs |
문제유형
- 그리디 - 두과목 모두 낮은 경우
- A 과목을 기준으로 정렬한 후
- A가 가장 높은 사람의 B 점수를 기록
- A 과목을 순회하면서 B점수를 보다 높은값으로 갱신하며
- 두과목 모두 낮은 경우 조회
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2143 두 배열의 합 쉬운 풀이(C++/CPP) (0) | 2021.02.15 |
|---|---|
| 백준 2565 전깃줄 쉬운 풀이(C++/CPP) (0) | 2021.02.15 |
| 백준 1937 욕심쟁이 판다 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |
| 백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP) (0) | 2021.02.14 |