[백준 3020] 개똥벌레

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

 

1. 문제 이해

개똥벌레가 장애물로 가득찬 동굴 들어감. 동굴의 길이 N, 높이 H 

첫번째 장애물 항상 석순, 다음 종유석과 석순 번갈아가며 등장

개똥벌레는 지나갈 구간 일직선으로 지나가면서 장애물 안 피하고 파괴함.

개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구해라

 

2. 조건

동굴의 길이 N은 항상 짝수

 

3. 풀이

1) 첫번째 풀이

홀수(석순)는 오름차순, 짝수(종유석)는 내림차순으로 정렬하고

개똥벌레의 위치에 따라 지나가는 것들 다 더한 다음 배열에 저장하고, 

파괴해야하는 최솟값과 그 구간이 몇개인지를 센다.

 

짝수는 h-i+1보다 크거나 같으면 그 구간을 지나가는 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 500002

int main() {
    int n, h, num;
    vector<int> odd, even;
    int section[MAX];
    cin >> n >> h;

    for (int i = 1; i <= n; i++) {
        cin >> num;
        if (i % 2 == 1) { //홀수
            odd.push_back(num);
        } else {
            even.push_back(num);
        }
    }
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end(), greater<>());


    for (int i = 1; i <= h; i++) {
        int sum = 0;

        for (auto o: odd) {
            if (o >= i) {
                sum += 1;
            }
        }


        for (auto e: even) {
            if (e >= (h - i + 1)) {
                sum += 1;
            }
        }

        section[i - 1] = sum;
    }

    int minSize = MAX;
    int cnt = 0;
    for (int i = 0; i < h; i++) {
        if (minSize == section[i]) {
            cnt++;
            continue;
        }
        if(minSize > section[i]){
        	minSize = section[i];
            cnt = 0;
        }
    }

    cout << minSize << " " << cnt + 1;

    return 0;
}

그치만 시간 초과...ㅠ

(200,000 X 500,000)

 

2) 두번째 풀이

앞전에 구한 짝수의 h-i+1은 즉, 그 곳에 장애물이 위치한다는 의미이다.

앞서 계속 반복해 계산해서 오류가 난 것이기 때문에

누적합으로 이용하면 되겠다고 생각 !

(odd, even 헷갈려서 bottom, top으로 변경)

#include <iostream>
using namespace std;

#define MAX 500002
int n, h, num;
int top[MAX];
int bottom[MAX];
int result[MAX];

int main() {
    cin >> n >> h;

    for (int i = 1; i <= n; i++) {
        cin >> num;
        if (i % 2 == 1) {
            bottom[num]++;
        } else {
            top[h - num + 1]++;
        }
    }

	//누적합
    for (int i = h; i >= 1; i--) {
        bottom[i] += bottom[i + 1];
    }
    for (int i = 0; i < h; i++) {
        top[i + 1] += top[i];
    }

    int minSize = MAX, cnt;
    for (int i = 1; i <= h; i++) {
        result[i] = bottom[i] + top[i];
        if (result[i] < minSize) {
            minSize = result[i];
            cnt = 1;
        } else if (result[i] == minSize) {
            cnt += 1;
        }
    }

    cout << minSize << " " << cnt;

    return 0;
}