일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 세그먼트트리
- 그리디
- 동적계획법
- 이분탐색
- 분할정복
- 누적합
- 다이나믹프로그래밍
- 재귀
- backtracking
- 백준
- priority_queue
- 유니온파인드
- DP
- 알고리즘문제해결전략
- 완전탐색
- 종만북
- 문자열
- 백트래킹
- stack
- BFS
- 분리집합
- 너비우선탐색
- BOJ
- acm
- union-find
- 스택
- Greedy
- Algospot
- DFS
- 알고스팟
- Today
- Total
DAMPER's 낙서장
[ALGOSPOT] 너드인가, 너드가 아닌가? 2 (NERD2) 본문
algospot.com/judge/problem/read/NERD2
<문제>
대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 예상되고 있습니다. 그러나 채점관을 할 자원 봉사자는 예년과 똑같이 5명뿐이라, 이 사람들을 대회에 다 참가시킬 수는 없습니다. 따라서 올해에도 참가 신청을 한 사람 중 진정한 프로그래밍 너드들만을 대회에 참가할 수 있도록 받아 주기로 했습니다.
종만의 새로운 이론에 따르면, 어떤 사람의 너드 지수는 다음 두 가지 값에 의해 결정됩니다.
- 알고스팟 온라인 채점 시스템에서 푼 문제의 수 p
- 밤 새면서 지금까지 끓여먹은 라면 그릇 수 q
이 이론에 따르면 어떤 참가 신청자 a 의 문제 수 pa 와 그릇 수 qa 를 다른 참가 신청자 b 의 문제 수 pb 와 그릇 수 qb 에 각각 비교했을 때, pa < pb, qa < qb 라면 참가 신청자 a 는 너드일 가능성이 없습니다. 조직위는 너드일 가능성이 있는 사람들만을 대회에 받아주기로 했습니다.
한 사람의 참가 가능 여부는 다른 사람들에 의해 결정되기 때문에, 대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀝니다. 예를 들어 다음과 같은 4명의 사람들이 순서대로 참가 신청을 했다고 합시다.
참가자종만재훈효승광규
문제 수 | 72 | 57 | 74 | 64 |
라면 그릇 수 | 50 | 67 | 55 | 60 |
종만과 재훈이 순서대로 대회 참가 신청을 하면 대회에 참가할 수 있는 사람의 수는 각각 1, 2 로 늘어나지만, 효승이는 문제 수도 라면 그릇 수도 종만보다 많으므로 효승이 참가 신청을 한 시점에서 종만은 더 이상 대회에 참가할 수 없습니다. 따라서 이 네 명이 참가 신청을 할 때마다 참가 가능자의 수는 1, 2, 2, 3으로 변합니다.
이렇게 각 사람이 참가 신청을 할 때마다 대회에 참가할 수 있는 사람들의 수가 어떻게 변하는지 계산하는 프로그램을 작성하세요.
<입력>
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 참가 신청한 사람들의 수 N (1 <= N <= 50000) 이 주어집니다. 그 후 N 줄에 각 2개의 정수로 각 사람의 문제 수 pi 와 라면 그릇 수 qi 가 참가 신청한 순서대로 주어집니다 (0 <= pi,qi <= 100000) . 두 사람의 문제 수나 라면 그릇 수가 같은 경우는 없다고 가정해도 좋습니다.
입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.
<출력>
각 사람이 참가 신청을 할 때마다 대회 참가 자격이 되는 사람의 수를 계산한 뒤, 각 테스트 케이스마다 그 합을 출력합니다.
<예제 입력>
2
4
72 50
57 67
74 55
64 60
5
1 5
2 4
3 3
4 2
5 1
<예제 출력>
8
15
<실수 한 부분>
삭제하는 과정에서 실수가 발생했다.
lower_bound로 찾고, map을 처음(map.begin())부터 찾은 곳의 바로 전(k라 칭하겠음.)까지 순회하면서 조건에 맞지 않는 사람을 삭제했다.
이렇게 했을 때 삭제 작업 자체가 O(NlogN) 작업이 되어버려 시간초과가 발생한다.
하지만 k에서부터 처음까지 찾으면 시간초과가 발생하지 않는다.
처음부터 k까지 순회를 하면, p보다 작은 부분을 순회한다는 것인데,
해당 구간 모두에서 q보다 작은 지 확인해야한다.
하지만 k에서부터 처음까지 순회하면서 q보다 작은 지 확인해 삭제하다가 q보다 큰 부분이 발생(qA라 칭하겠음.)하면 해당 구간을 모두 탐색하지 않고 거기서 끝내면 된다.
왜냐면 qA보다 전의 qi들은 항상 qA보다 작을 수 없다. 이유는 qA에 해당하는 key값(pA)보다 pi값이 더 작은데 qA보다 qi가 작은 것들이 map에 존재할 수 없기 때문이다. {pA, qA}가 삽입될 때 삭제되었거나, 아예 map에 들어오지 못했다.
그러므로 k부터 begin()까지 탐색할 경우, 해당 구간 모두를 항상 탐색할 필요가 없다.(최악의 경우 모두 탐색)
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
47
48
49
50
51
52
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int tc;
cin>>tc;
while(tc--)
{
int n;
cin>>n;
map<int, int> mp;
int ans = 0;
for(int i=0;i<n;i++)
{
int p, q;
cin>>p>>q;
auto it = mp.lower_bound(p);
if(it == mp.end() || q>it->second)
{
if(it != mp.begin())
{
--it;
for(auto k = it;;k--)
{
if(k->second > q) break;
if(k == mp.begin())
{
mp.erase(k);
break;
}
k = mp.erase(k);
}
}
mp[p] = q;
}
ans += mp.size();
}
cout<<ans<<endl;
}
return 0;
}
|
cs |
'Problem Solving > 알고리즘 문제해결전략' 카테고리의 다른 글
[ALGOSPOT] 변화하는 중간값 (RUNNINGMEDIAN) (0) | 2021.02.02 |
---|---|
[ALGOSPOT] 삽입 정렬 뒤집기 (INSERTION) (0) | 2021.02.02 |
[ALGOSPOT] 요새 (FORTRESS) (0) | 2021.01.31 |
[ALGOSPOT] 트리 순회 순서 변경 (TRAVERSAL) (0) | 2021.01.26 |
[ALGOSPOT] 외계 신호 분석 (ITES) (0) | 2021.01.23 |