백준 25634, 전구 상태 뒤집기

개요

문제 링크
골드 5, DP
연속된 부분 수열의 상태 변경을 통합 누적합의 최댓값

---

접근

1. 아무래도 어렵게 짜는데 도가 튼 듯 하다. 처음에는 연산을 한 전구에만 수행하는 줄 알았는데, 연속한 구간에 대해 한 번 수행한다는 것을 알고 뇌정지 옴. 세그트리인가? 하는 생각이 스쳐지나가고 그랬음.

2. dp를 쓰는데, dp[i][0]은 i까지 연산을 안 쓰고 온 합, dp[i][1]은 i까지 연산을 연속된 구간에 쓰면서 온 합의 최댓값으로 했다.

3. dp[i][0]은 단순 누적합이라 아래처럼 해주면 됨.

   dp[i][0] = dp[i-1][0] + a[i]*b[i]

4. 그러면 dp[i][1]은? 이 부분을 원래 골5정도면 쉽게 주는데 개인적으로 이런 문제를 안접해봐서 그런지 어렵게 짰음.

   dp[i][1] = max(dp[i][0]+a[i]*!b[i], dp[i][1]+a[i]*!b[i])

   이게 무엇인가 하니, 이전까지 연산을 안 쓰고 왔으면서 새로 쓴 경우가 왼쪽이고, 이전까지 연산을 쓰면서 지금도 쓴 경우가 오른쪽이다. 이걸 계산해주면 i번째까지 어떤 연속구간에 대해 연산을 쓴 경우 최대 누적합을 구해줄 수 있다.

5. 마지막으로 정답은 무조건 연산을 1회 수행해야 하니 dp[i][1]과 오른쪽 누적합을 비교해 업데이트

---

Pseudo code

sum_right[i] = sum(i, n)
for (i = 1~n)
    dp[i][0] = dp[i-1][0] + a[i]*b[i]

    new_action = dp[i-1][0] + a[i]*!b[i]
    continue_action = dp[i-1][1] + a[i]*!b[i]
    dp[i][1] = max(new_action, continue_action)

    answer = max(dp[i][1] + sum_right[i+1])

---

Source code

#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int a, b;
} bulb;

int main() {
    int n;
    cin >> n;
    bulb a[n];
    int sum[n+1];
    for (int i=0; i<n; i++)
        cin >> a[i].a;
    for (int i=0; i<n; i++)
        cin >> a[i].b;
    sum[n] = 0;
    sum[n-1] = a[n-1].a*a[n-1].b;
    for (int i=n-2; i>=0; i--)
        sum[i] = sum[i+1]+a[i].a*a[i].b;

    int dp[n+1][2];
    dp[0][!a[0].b] = a[0].a;
    dp[0][a[0].b] = 0;
    int ans = dp[0][1]+sum[1];
    for (int i=1; i<n; i++) {
        int p = a[i].b*a[i].a;
        int q = !a[i].b*a[i].a;
        dp[i][0] = dp[i-1][0]+p;
        dp[i][1] = max(dp[i-1][0]+q, dp[i-1][1]+q);
        ans = max(ans, dp[i][1]+sum[i+1]);
    }
    cout << ans;
}