[알고리즘] 백준 3020 - 개똥벌레 (C++)

[문제 링크] : https://www.acmicpc.net/problem/3020

#include <iostream>
using namespace std;

int U[500001];
int D[500001];

int main(){
    int N, H, inp;
    cin >> N >> H;

    for(int i=0; i<N; i++){
        cin >> inp;
        if(i % 2 == 0){
            D[inp]++;
        }
        else{
            U[H - inp + 1]++;
        }
    }

    for(int i=1; i<=H; i++){
        U[i] += U[i-1];
        D[H-i] += D[H-i+1];
    }

    int Ans = 1234567890;
    int Cnt = 0;

    for(int i=1; i<=H; i++){
        if(U[i] + D[i] < Ans){
            Cnt = 1;
            Ans = U[i] + D[i];
        }
        else if(U[i] + D[i] == Ans){
            Cnt++;
        }
    }

    cout << Ans << " " << Cnt << "\n";

    return 0;
}