BOJ 3020 - 개똥벌레(C++)

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

3020번: 개똥벌레

풀이

algorithm 라이브러리에서 제공하는 이진탐색 함수인 lower_bound, upper_bound를 이용하여 풀 수 있음

* 이진탐색을 위해서는 오름차순 정렬이 되어 있어야함

lower_bound(begin, end, target) : target 값 이상의 숫자가 배열 몇 번째에 있는지 탐색

upper_bound(begin, end, target) : target 값을 초과하는 숫자가 배열 몇 번째에 있는지 탐색

 

석순과 종유석을 나눠서 배열에 저장, 정렬

1 ~ N 까지의 높이에 대해 포함되는 개수를 확인(종유석의 경우 N-v를 초과해야 벌레가 부딪침)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, H;
int up[100001];
int down[100001];

int main() {
    cin >> N >> H;
    for (int i = 0; i < N / 2; i++) {
        cin >> down[i] >> up[i];
    }

    sort(up, up + (N / 2));
    sort(down, down + (N / 2));
    
    int res = 987654321;
    int cnt = 0;
    for (int i = 1; i <= H; i++) {
        int val1 =(N/2) - (lower_bound(down, down + (N / 2), i) - down); //해당 위치에 포함되는 석순의 수
        int val2 = (N/2) - (upper_bound(up, up + (N / 2), (H - i)) - up);//해당 위치에 포함되는 종유석의 수
        int val = val1 + val2;
        
        if (val < res) {
            res = val;
            cnt = 1;
        }
        else if (val == res) {
            cnt++;
        }
    }
    cout << res << ' ' << cnt;
    return 0;
}

이진 탐색을 사용하지 않고 단순 누적합을 이용하면 시간이 더 줄어 들거라 생각해서 풀어봄

위의 풀이와 비슷하지만 위의 배열은 입력받은 순으로 높이를 저장, 아래 코드는 해당 높이에 해당하는 석순/종유석의 개수

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N, H;
int up[500001];
int down[500001];

int main() {
    cin >> N >> H;
    int height;
    for (int i = 0; i < N; i++) {
        cin >> height;
        if (i % 2 == 0)
            down[height]++;
        else
            up[height]++;
    }

    int downSum = 0;
    for (int i = 1; i <= H; i++) {
        downSum += down[i];
    }

    int upAdd = up[H];
    int downAdd = down[1];
    int MIN = downSum + upAdd;//높이가 1일때 포함되는 석순과 종유석의 개수
    int cnt = 1;
    for (int i = 2; i <= H; i++) {
        upAdd += up[H - i + 1];//높이가 올라갈수록 포함되는 석순은 증가하기 때문에 누적
        //종유석의 경우 높이가 올라갈수록 포함되는 갯수가 줄어들것이기 때문에 종유석 총 갯수에서 빼기
        int val= (downSum - downAdd) + upAdd;
        
        if (val < MIN) {
            MIN = val;
            cnt = 1;
        }
        else if(val == MIN){
            cnt++;
        }
        downAdd += down[i];
    }
    
    cout << MIN << ' ' << cnt;
    return 0;
}

배열의 인덱스가 높이가 되버리기 때문에 메모리가 커질것은 예상(2800KB->5928KB)

시간이 줄어들기는 했지만 O(H x log(N/2)) 에서 O(H)로 변경된 만큼의 큰 차이라고는 느껴지지 않음(128ms->108ms)