백준 3020 개똥벌레 (C++)

3020번: 개똥벌레

이분 탐색과 누적 합을 이용한 문제이다. 먼저 문제 조건을 잘 읽어봐야 한다. N과 H가 주어지고 N 만큼 석순과 종유석이 번갈아 주어지게 된다. 이를 각각 s와 j 배열에 해당 위치마다 카운트를 해주었다. j는 종유석이기 때문에 높이에서 뺀 만큼 위치를 카운트했다. 석순은 뒤에서, 종유석은 앞에서부터 카운트를 더해나가면서 해당 위치 장애물 개수를 저장해주었다. 이 후 반복문을 돌면서 해당 s와 j의 합을 result와 비교하면서 카운트해 이를 출력해주었다. 생각보다 아이디어가 안 떠오른 문제였다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, H;
int s[500001];
int j[500001];
int result = 987654321;
int c = 0;

void solution() {
    for (int i = 1; i <= H; i++) {
        s[H - i] += s[H - i + 1];
        j[i] += j[i - 1];
    }

    for (int i = 1; i <= H; i++) {
        if (s[i] + j[i] < result) {
            c = 1;
            result = s[i] + j[i];
        }
        else if (s[i] + j[i] == result) {
            c++;
        }
    }

    cout << result << " " << c;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> H;

    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;

        if (i % 2 == 0) {
            s[a]++;
        }
        else {
            j[H - a + 1]++;
        }
    }

    solution();

    return 0;
}