[BOJ 백준] 개똥벌레(3020) C++

 

링크 : https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

문제 설명 : 

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력 : 

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

 

예제 입력 : 

6 7
1
5
3
3
5
1

예제 출력 : 

2 3

 

 

접근법 : 

1) 어떻게 풀 것인가?

누적합에 대한 연산 --> 인덱스드트리 활용 가능

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 개똥벌레 3020 C++
#if 1
#pragma warning(disable:4996)
#include<cstdio>

using namespace std;

#define SIZE_OF_ARRAY (200005)
#define SIZE_OF_TREE  (1100000)

int n, h, num;
int tree[SIZE_OF_TREE];
int OFFSET = 1;

void update(int st_idx, int ed_idx) {
    st_idx += OFFSET;
    ed_idx += OFFSET;
    while (st_idx <= ed_idx) {
        if (st_idx % 2 == 1) tree[st_idx++] += 1;
        if (ed_idx % 2 == 0) tree[ed_idx--] += 1;
        st_idx /= 2; ed_idx /= 2;
    }
}

int query(int idx) {
    int sum = 0;
    idx += OFFSET;
    while (idx > 0) {
        sum += tree[idx];
        idx /= 2;
    }
    return sum;
}

int main() {
    scanf("%d %d", &n, &h);
    while (OFFSET < h) {
        OFFSET *= 2;
    }
    OFFSET -= 1; // internal 노드의 개수
    for (int i = 1; i <= n; i++) { // index는 1부터 시작
        scanf("%d", &num);
        if (i % 2 == 1) { // 석순
            update(h - num + 1, h);
        }
        else if (i % 2 == 0) { //  종유석
            update(1, num);
        }
    }
    int min = 500005;
    int cnt = 0;
    for (int i = 1; i <= h; i++) {
        int result = query(i);
        if (result < min) {
            min = result;
            cnt = 1;
        }
        else if (result == min) {
            cnt++;
        }
    }
    printf("%d %d\n", min, cnt);
    return 0;
}
#endif