B. Cutting

cnt(odd) == cnt(even) 인 구간을 나눌 때 일정 cost가 필요한데 이 cost의 상한선을 B로 설정했을 때 최대 몇개의 구간을 나눌 수 있는지 물어보는 문제다.

a[i]를 입력받으면서 odd, even인지 검사하고 같아지는 위치에서 cost를 vector에 넣는다.

이걸 정렬하고 낮은값부터 누적합을 해나가면서 B를 넘어가는 시점에 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, b, a[101], cnt;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> b;
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        a[i] % 2 ? cnt++ : cnt--;
        if (!cnt)
            ans.push_back(abs(a[i + 1] - a[i]));
    }
    sort(ans.begin(), ans.end());
    for (int i = 1; i < ans.size(); ++i)
        ans[i] += ans[i - 1];
    int result;
    for (result = 0; result < ans.size() && ans[result] <= b; ++result);
    cout << result << '\n';
    return 0;
}