백준 3020 개똥벌레 혼내주기

 

누적합을 개념문제를 풀고 처음으로 푼 문제. 석순과 종유석의 길이마다 개수를 저장한 뒤, 가장 긴 녀석부터 짧은 녀석까지 누적합으로 더해준다. 이후 석순과 종유석에 알맞게 더해주면 된다.
다른 사람들의 코드를 보니 대부분 이분탐색으로 풀었다. 내가 누적합 문제라는 것을 모르고 풀었으면 나도 그랬을까?

 

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

int arr[2][500001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, h, tmp;
    cin >> n >> h;
    for(int i = 1; i <= n; ++i){
        cin >> tmp;
        arr[i%2][tmp]++;
    }

    for(int i = h-1; i > 0; --i){
        arr[1][i] = arr[1][i+1] + arr[1][i];
        arr[0][i] = arr[0][i+1] + arr[0][i];
    }

    int mn = 1e9;
    for(int i = 1, j = h; i <= h; ++i, --j){
        arr[1][i] = arr[1][i] + arr[0][j];
        mn = min(mn, arr[1][i]);
    }
    int cnt = 0;
    for(int i = 1; i <= h; ++i)
        if(arr[1][i] == mn) cnt++;
    
    cout << mn << " " << cnt;
}