Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

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

 

3755번: Double Queue

The new founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania, and using modern information technologies. As usual, each client of the bank is identified by a

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 두 개 선언해, 오름차순과 내림차순으로 각각 저장합니다.

 

2. visited 배열을 만들어 현재 K 고객이 서비스를 이용한 상태인지 그렇지 않은 상태인지 저장합니다.

 

3. 입력되는 명령어에 따라 값을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int visited[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int cmd;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> greater;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> less;
 
    while (1) {
        cin >> cmd;
 
        if (cmd == 1) {
            int K, P;
            cin >> K >> P;
            greater.push({ P,K });
            less.push({ P,K });
            visited[K] = 0;
        }
        else if (cmd == 2) {
            while (1) {
                if (less.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = less.top().second;
                less.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else if (cmd == 3) {
            while (1) {
                if (greater.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = greater.top().second;
                greater.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else {
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
반응형

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

 

21939번: 문제 추천 시스템 Version 1

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. set 자료구조를 활용하여 문제의 난이도와 번호를 insert 합니다.

 

2. 문제 번호에 따라 난이도를 알 수 있도록 level 배열을 만들어 저장합니다.

 

3. 가장 어려운 난이도의 문제는 set 자료구조의 제일 마지막에 있고, 가장 쉬운 난이도의 문제는 set 자료구조의 제일 앞에 있으므로 명령문에 따라 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<set>
#include<string>
 
using namespace std;
 
int N, M;
int level[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    set<pair<int,int>> s;
 
    for (int i = 0; i < N; i++) {
        int P, L;
        cin >> P >> L;
 
        level[P] = L;
        s.insert({ L,P });
    }
    
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        string cmd;
        cin >> cmd;
 
        if (cmd == "add") {
            int P, L;
            cin >> P >> L;
 
            level[P] = L;
            s.insert({ L,P });
        }
        else if (cmd == "recommend") {
            int x;
            cin >> x;
 
            if (x == 1) {
                cout << (*s.rbegin()).second << '\n';
            }
            else {
                cout << (*s.begin()).second << '\n';
            }
        }
        else {
            int P;
            cin >> P;
 
            s.erase({ level[P],P });
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
반응형

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

 

17612번: 쇼핑몰

입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 이용하여 계산대로 들어가는 순서를 정합니다.

 

2. priority_queue에서 하나씩 빼고 넣으면서 뺀 값을 vector<node> 에 넣습니다.

 

3. 계산대에서 나오는 순서대로 vector<node>를 정렬합니다.

 

4. vector<node>를 for문을 통해 돌면서 주어진 대로 계산해 ans에 저장합니다.

 

5. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct node {
    int K;
    ll num;
    int w;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (left.w == right.w) return left.K < right.K;
        return left.w < right.w;
    }
};
 
int N, k;
vector<node> seq;
 
bool cmp2(node left, node right)
{
    if (left.w == right.w) return left.K > right.K;
    return left.w < right.w;
}
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    queue<pair<ll,int>> q;
    scanf("%d %d", &N, &k);
 
    for (int i = 0; i < N; i++) {
        int b;
        ll a;
        scanf("%lld %d", &a, &b);
        q.push({a,b});
    }
 
    for (int i = 1; i <= k; i++) {
        pq.push({ i,q.front().first,q.front().second });
        q.pop();
 
        if (q.empty()) break;
    }
 
    ll ans = 0;
 
    while (!pq.empty()) {
        const int K = pq.top().K;
        const ll num = pq.top().num;
        const int w = pq.top().w;
        pq.pop();
 
        seq.push_back({ K,num,w });
 
        if (!q.empty()) {
            pq.push({ K,q.front().first, q.front().second + w });
            q.pop();
        }
    }
 
    sort(seq.begin(), seq.end(), cmp2);
 
    for (ll i = 0; i < seq.size(); i++) {
        ans += seq[i].num * (i + 1);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
반응형

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

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. 비재귀 세그먼트 트리를 이용하여 각 구간의 최솟값을 구해주고, 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[10000001];
int N, L;
 
int getTree(int left, int right)
{
    left += N;
    right += N;
    int ret = 1000000000;
 
    while (left <= right) {
        if (left & 1) {
            ret = min(arr[left], ret);
            left += 1;
        }
        if (~right & 1) {
            ret = min(arr[right], ret);
            right -= 1;
        }
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> L;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[N + i];
    }
 
    for (int i = N - 1; i >= 1; i--) {
        arr[i] = min(arr[i << 1], arr[i << 1 | 1]);
    }
 
    for (int i = 0; i < N; i++) {
        cout << getTree(max(0, i - L + 1), i) << ' ';
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
반응형

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

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 만들고, 시간을 기준으로 오름차순으로 정렬하되 시간이 같으면 끝나는 시간이 앞으로 오도록 우선순위를 정합니다.

 

2. pq에서 값을 하나씩 꺼내면서 temp에 시작하는 시간이면 1을 더하고, 끝나는 시간이면 1을 빼줍니다.

 

3. temp의 값 중 가장 큰 값을 ans에 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N;
 
struct Class {
    char cur;
    int time;
};
 
struct cmp {
    bool operator()(Class right, Class left) {
        if (right.time == left.time) {
            if (left.cur == 'e') {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return left.time < right.time;
        }
    }
};
 
int main()
{
    priority_queue<Class, vector<Class>, cmp> pq;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int S, T;
        scanf("%d %d", &S, &T);
 
        pq.push({ 's', S});
        pq.push({ 'e', T});
    }
 
    int ans = 0;
    int temp = 0;
 
    while (!pq.empty()) {
        const char cur = pq.top().cur;
        pq.pop();
 
        if (cur == 's') temp++;
        else temp--;
 
        ans = max(ans, temp);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
반응형

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

 

20311번: 화학 실험

화학 실험을 하던 윤이는 일렬로 나열해 놓은 N개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 시험관의 개수를 입력받고, priority_queue에 내림차순으로 정렬합니다.

 

2. 만약 수가 가장 많은 시험관의 개수가 (N + 1) / 2개보다 많다면 -1을 출력합니다.

 

3. pq에서 값을 하나씩 뽑아 arr 배열에 시험관의 색깔 번호를 넣습니다.

 

4. 0 ~ (N + 1) / 2 - 1까지 arr 배열의 값을 ans의 0부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

5. (N + 1) / 2 ~ N - 1까지 arr배열의 값을 ans의 1부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

6. ans 배열을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, K;
vector<int> arr;
int ans[300000];
 
int main()
{
    priority_queue<pair<int, int>>pq;
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i <= K; i++) {
        int c;
        scanf("%d", &c);
 
        pq.push({ c,i });
    }
 
    if (pq.top().first > (N + 1) / 2) {
        printf("-1");
        return 0;
    }
 
    while (!pq.empty()) {
        const int cnt = pq.top().first;
        const int num = pq.top().second;
        pq.pop();
 
        for (int i = 0; i < cnt; i++) {
            arr.push_back(num);
        }
    }
    
    int num = 0;
 
    for (int i = 0; i < (N + 1) / 2; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    num = 1;
 
    for (int i = (N+1)/2; i < N; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    for (int i = 0; i < N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 11000번 - 강의실 배정 (C++)  (0) 2023.04.22
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
반응형

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

 

1781번: 컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 데드라인과 컵라면 개수를 입력받고 arr 배열에 저장합니다.

 

2. arr배열을 데드라인을 기준으로 오름차순으로 정렬합니다.

 

3. 1부터 N까지 for문을 통해 돌면서 priority_queue에 넣어주고, arr[ i ]의 데드라인보다 pq.size()가 크면 pq.pop()을 해줍니다.

 

4. pq에 있는 모든 값을 더하고, 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int ans;
 
int main()
{
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<pair<int, int>> arr;
    
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr.push_back({ a,b });
    }
 
    sort(arr.begin(), arr.end());
 
    for (int i = 0; i < N; i++) {
        pq.push(arr[i].second);
        
        if (arr[i].first < pq.size()) {
            pq.pop();
        }
    }
 
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
반응형

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

 

13975번: 파일 합치기 3

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수를 입력받을 때 priority_queue에 오름차순으로 넣습니다.

 

2. pq에서 맨 앞의 두 수를 뽑아 더한 값을 ans에 더하고, 그 값을 다시 pq에 넣습니다.

 

3. pq가 빌 때까지 위 과정을 반복합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#define ll long long
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int K;
        scanf("%d", &K);
 
        priority_queue<ll, vector<ll>, greater<ll>> pq;
 
        ll ans = 0;
 
        for (int i = 0; i < K; i++) {
            ll num;
            scanf("%lld", &num);
 
            pq.push(num);
        }
 
        while (1) {
            const ll a = pq.top();
            pq.pop();
            const ll b = pq.top();
            pq.pop();
 
            ans += a + b;
 
            if (pq.empty()) break;
 
            pq.push(a + b);
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
반응형

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

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. struct를 만들어 입력된 수와 절댓값을 저장합니다.

 

2. pq에 절댓값이 낮은 순으로 정렬하고, 같다면 수가 낮은 순으로 정렬합니다.

 

3. 0이 입력되면 pq에서 하나씩 뽑아가면서 출력합니다.

 

[ 소스 코드 ]

 

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
#include<cstdio>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int num;
    int absolute;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (right.absolute == left.absolute) return left.num < right.num;
        return left.absolute < right.absolute;
    }
};
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    int N;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        if (x != 0) {
            pq.push({ x,abs(x) });
        }
        else {
            if (!pq.empty()) {
                printf("%d\n", pq.top().num);
                pq.pop();
            }
            else {
                printf("%d\n", 0);
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
반응형

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

티스토리툴바