백준 25634번 - 전구 상태 뒤집기 (C++)

https://www.acmicpc.net/problem/25634

25634번: 전구 상태 뒤집기

 

문제 조건

- 한 시퀀스가 모두 바뀌었을 때를 가정한다. 길이가 3이면 

1,2,3,1~2, 3~4, 1~3 이렇게 모든 전구를 바꾸어야한다. 반드시 단 1번은 바꾸어야한다.

 

내 접근

- dp로풀어야한다. 그리고 누적합으로 구하는 것인데 어떻게 하는지 모르겠어서 일단 dp로 생각해보기로 했다. 그러나

dp[index] = index까지의 최적합

으로 구하기에는 따져야할 것이 너무도 많다. 그러므로 관점을 바꿔서 먼저 전구가 모두 켜져있는 것의 합을 sum을 구한다. 그리고 

dp[index] = index에서 sum에다가 더할 수 있는 최대값

으로 설정한다. 그렇다고 한다면 만약 전구가 켜져있는 상태라면

-> 이번 것의 전구를 끔 or 끄지 않음

 

만약 전구를 껐다면 이전 의 최대 합 DP[index - 1] - Now 와 -Now 를 비교한다. 해석하면 이전에 이어서 이번 전구까지 끌것이다. 혹은 나만 끄겠다. 새로만들자 로 해석할 수 있다. 

 

꺼져있는 상태였다면 더 쉽다. 이전것과 더하거나 이전것을 모두 놔두고 지금것만 켰을 때 더 큰 것을 선택하면된다.

 

그렇다면 마지막 정답은 sum + max_DP 가 된다.

 

관점을 바꾸는 것이 매우 어려웠던 문제이다. 근데 누적합, 연속합을 쓰면 더 쉽게 풀리는 듯 하다.

 

#include <iostream>

using namespace std;

int dp[200001];
int light[200001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    
    int stat;
    
    for(int i = 0; i < N; i++){
        cin >> light[i + 1];
    }
    int answer = 0;
    for(int i = 1; i <= N; i++){
        cin >> stat;
        if(stat == 1){
            answer += light[i];
            dp[i] = max(dp[i - 1]  - light[i], -light[i]);
        }else{
            dp[i] = max(dp[i - 1] + light[i], light[i]);
        }
    }
    int max_light = -1313213123;
    for(int i = 1; i <= N; i++){
        max_light = max(max_light, dp[i]);
    }
    
    cout << answer + max_light << '\n';
}