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

문제링크 : https://www.acmicpc.net/problem/25634

25634번: 전구 상태 뒤집기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll N, a[200001], b[200001], dp[200001], sum;

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

    cin >> N;
    for(int i=1; i<=N; i++) cin >> a[i];
    for(int i=1; i<=N; i++) 
    {
        cin >> b[i];
        if(b[i]) sum+=a[i]; //누적합
    }

    for(int i=1; i<=N; i++)
    {
        if(b[i]) //ON->OFF
        {
            dp[i] = -a[i]; //변환
            dp[i] = max(dp[i-1]-a[i], dp[i]); //앞에꺼까지 바꾼게 큰지, 지금 값만 바꾼게 큰지 비교
        }
        else  //OFF->ON
        {
            dp[i] = a[i]; //변환
            dp[i] = max(dp[i-1]+a[i], dp[i]); //앞에꺼까지 바꾼게 큰지, 지금 값만 바꾼게 큰지 비교
        }
    }

    ll maxv = dp[1];
    for(int i=1; i<=N; i++) maxv = max(maxv, dp[i]); //가장 큰 증감수치 저장
    cout << maxv + sum; //기존 합 + 증감수치
    return 0;
}

 

연속한 전구를 한 개 이상 선택하여 상태를 뒤집으므로 가능한 경우는 다음과 같다.

예제 3
3 2 5
1 0 1

0 0 1 //맨 앞 뒤집음
0 1 1 //맨 앞 + 이어서 뒤집음
0 1 0 //맨 앞 + 이어서 + 이어서 뒤집음

1 1 1 //두 번째 뒤집음
1 1 0 //두 번째 + 이어서 뒤집음

1 0 0 //마지막 뒤집음

 

현재 값만을 뒤집는 것은 간단하게 스위치 여부에 따라 해당 위치의 값을 할당하거나 빼주면 된다.

(dp[i] = a[i] or -a[i])

추가로 고려해야 할 것이 이어서 뒤집는 경우를 체크해주는 것이다.

이를 위해 dp식을 이용한다.

 

먼저 입력받은 값들을 토대로 현재 스위치 ON, OFF에 따라 스위치 전환을 실시한다.

그리고 해당 값(스위치 전환한 값)을 현재 dp에 저장해준다.

그리고 이전 위치의 dp값 + 변환 수치가 큰지 현재 dp 값이 큰 지 비교를 하게 된다.

이는 (그전값 변환 + 현재 값 변환)이 더 나은지, (현재 값만 변환)이 더 나은지 확인하기 위함이다.

예제 3
3 2 5
1 0 1

0 0 1 //맨 앞 뒤집음
dp[1] = -3;

0 1 1 //맨 앞 + 두 번째 뒤집음
dp[2] = -3+2 = -1;
1 1 1 //두 번째만 뒤집음
dp[2] = 2; (MAX)

<이전 경우에서 두 번째만 뒤집는 경우가 최대이므로 이를 반영함>
0 1 0 //맨 앞 + 이어서 + 이어서 뒤집음 
dp[3] = 2-5=-3;
1 1 0 //두 번째 + 이어서 뒤집음
dp[3] = 2-5=-3;
1 0 0 //마지막 뒤집음
dp[3] = -5;

MAX = 2; (최대 증감수치)

 

이렇게 저장된 dp 값은 원래 스위치에서 변환된 가장 큰 값을 담기에 가능한 가장 큰 증감수치를 담게 된다.

우리가 구하고자 하는 것은 최대값이기에 기존에 구했던 누적합 + 누적합 기준 가장 큰 증감수치를 하여 출력하게 된다.