반응형

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

 

14449번: Balanced Photo

The first line of input contains N. The next N lines contain h1…hN, each a nonnegative integer at most 1,000,000,000.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. arr 배열에 키를 저장하고, vector<int> h에 입력으로 주어진 모든 키를 push 합니다.

 

2. h를 오름차순으로 정렬합니다.

 

3. 0부터 N - 1까지 arr 배열을 돌면서 해당 값의 idx를 lower_bound를 통해 구합니다.

 

4. idx + 1 ~ e * N - 1의 구간합을 통해 왼쪽에 있는 값들 중 큰 값을 구하고, cntL에 저장합니다.

 

5. N - 1부터 0까지 위의 3, 4와 같은 방식으로 구하고 cntR에 구간합을 저장합니다.

 

6. cntL[ i ] * 2 < cntR[ i ] 이거나 cntL[ i ] > cntR[ i ] * 2이면 ans++를 해줍니다.

 

7. 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
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[100000];
int cntL[100000];
int cntR[100000];
int segTree[200000];
vector<int> h;
int ret;
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int L, int R)
{
    int ret = 0;
 
    while (L <= R) {
        if (L & 1) {
            ret += segTree[L];
            L++;
        }
        if (~R & 1) {
            ret += segTree[R];
            R--;
        }
        
        L >>= 1;
        R >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        h.push_back(arr[i]);
    }
 
    sort(h.begin(), h.end());
 
    for (int i = 0; i < N; i++) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntL[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    fill(segTree, segTree + 2 * N, 0);
 
    for (int i = N - 1; i >= 0; i--) {
        auto idx = lower_bound(h.begin(), h.end(), arr[i]) - h.begin();
        updateTree(idx + N);
 
        cntR[i] = getTree(N + idx + 1, 2 * N - 1);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        int L = cntL[i];
        int R = cntR[i];
 
        if (L > R) {
            swap(L, R);
        }
 
        if (2 * L < R) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 14463번 - 소가 길을 건너간 이유 9 (C++)  (0) 2023.06.11
[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06

+ Recent posts

티스토리툴바