BOJ 25634 : 전구 상태 뒤집기

• 문제 링크 : boj.kr/25634
• 난이도 : G5
• 태그 : 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<ll> arr(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    ll sum = 0;
    bool check = true;
    for(int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        if(input) {
            sum += arr[i];
            arr[i] *= -1;
        }
        check &= input;
    }
    if(check) {
        ll M = -INF;
        for(int i = 1; i <= n; i++) {
            M = max(M, arr[i]);
        }
        cout << sum + M;
        return 0;
    }
    ll ans = 0;
    ll m = arr[0];
    for(int i = 1; i <= n; i++) {
        arr[i] += arr[i-1];
        m = min(m, arr[i]);
        ans = max(ans, arr[i]-m);
    }
    cout << sum + ans;

    return 0;
}

---

풀이

1~K까지 모든 전구를 뒤집었을 때 얻을 수 있는 밝기를 arr[K]라고 하자.

K를 포함하는 뒤집기에서 얻을 수 있는 최대 밝기는 arr[K] - Max(0, arr[1], arr[2], arr[3], ... arr[K])이다.

모든 K에 대한 최대 밝기의 최대값이 답이 된다.

 

단 꺼져있는 전구가 없는 경우엔 반드시 하나를 꺼야함에 유의한다.