반응형

https://www.acmicpc.net/problem/13334

 

13334번: 철로

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

선분의 최대 개수가 100,000개이므로 2중 for문을 돌리게 된다면 시간 초과가 뜹니다. 따라서 한 번의 탐색으로 답을 구해야 합니다.

 

먼저 선분을 끝점의 좌표를 기준으로 오름차순으로 정렬합니다. 그리고 앞에서부터 탐색을 시작하면서 선분의 길이가 d보다 작거나 같다면 priority_queue에 넣어줍니다. 그리고 끝 점의 좌표를 o라고 했을 때 o-d의 좌표보다 시작점의 좌표가 작다면 priority_queue에서 pop을 해줍니다.

 

이때 priority_queue의 size가 선분의 개수가 되고 위의 과정을 반복하면서 size의 최댓값을 저장해줍니다. 그리고 마지막에 최댓값을 출력해주면 쉽게 풀리는 문제였습니다.

 

[ 소스 코드 ]

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct line {
    int h;
    int o;
};
 
struct cmp {        //priority_queue는 선분의 시작 좌표가 작을수록 먼저 나오도록 설정
    bool operator()(line right, line left)
    {
        if (left.h == right.h) return left.o < right.o;
        return left.h < right.h;
    }
};
 
bool comp(line left, line right)    //선분들을 끝 좌표를 기준으로 오름차순 정렬
{
    if (left.o == right.o) return left.h < right.h;
    return left.o < right.o;
};
 
int n, d;
vector<line> arr;
priority_queue<line, vector<line>, cmp> pqAns;
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int h, o;
        scanf("%d %d", &h, &o);
        if (h < o) {        //좌푯값이 더 작은 값을 먼저 넣기
            arr.push_back({ h,o });
        }
        else {
            arr.push_back({ o,h });
        }
    }
 
    sort(arr.begin(), arr.end(), comp);
 
    cin >> d;
 
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        int h = arr[i].h;
        int o = arr[i].o;
 
        if (o - h <= d) {    //선분의 길이가 d를 넘지 않으면 push
            pqAns.push({ h,o });
        }
 
        while (!pqAns.empty())
        {
            int h = pqAns.top().h;
            if (h < o - d) {    //만약 제일 앞에 있는 선분이 길이L을 벗어나면 pop
                pqAns.pop();
            }
            else {
                break;
            }
        }
 
        if (ans < pqAns.size()) {    //pq의 사이즈가 선분의 개수
            ans = pqAns.size();
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26

+ Recent posts

티스토리툴바