BOJ 3020 C++

문제 접근

석순과 종유석의 누적합 배열을 만듭니다.
그리고 h가 7, 그리고 개똥벌레가 나는 높이가 1일때 부수는 수는 다음과 같습니다.

석순 전체 합 + 종유석 높이가 7이상인수

왜냐하면 1일때는 석순 전체를 부수고 종유석에서는 종유석의 높이가 7이라면 부서지겠죠 6이하라면 부서지지 않고요.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;
int n, h;

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

    // 입력 받기
    cin >> n >> h;
    vector<int> ob(n);
    for (int i = 0; i < n; i++)
        cin >> ob[i];
    
    // 상하 구분을 위한 배열 초기화
    vector<int> up(h + 1, 0);
    vector<int> lo(h + 1, 0);
    
    // 상하 구분
    for (int i = 0; i < n; i++)
    {
        if (i & 1)
            up[ob[i]]++;
        else
            lo[ob[i]]++;
    }
    
    // 누적합 계산
    for (int i = 1; i <= h; i++)
    {
        up[i] = up[i] + up[i - 1];
        lo[i] = lo[i] + lo[i - 1];
    }
    
    int ans = 2000002, cnt = 1;
    
    // 답 구하기
    for (int i = 1; i <= h; i++)
    {
        int tmp = lo[h] - lo[i - 1];
        tmp += up[h] - up[h - i];
        
        if (tmp < ans)
        {
            ans = tmp;
            cnt = 1;
        }
        else if (tmp == ans)
            cnt++;
    }
    
    // 결과 출력
    cout << ans << " " << cnt;
    
    return 0;
}