[백준 5527] 전구 장식 (C++)

5527번: 전구 장식

다이나믹 프로그래밍

---

가만히 머리로만 생각할 때는 잘 떠오르지 않다가 손으로 패턴이 될 만한것들을 적다보니까 풀 수 있었다.

 

가장 긴 증가하는 부분 수열 문제와 비슷한 느낌을 받았다.

증가하는 부분수열의 크기를 구할 때와 비슷하게 연속해서 나타나는 교대 패턴의 최대 길이를 구했다.

 

1번 예제 : 1 1 0 0 1 0 1 1 1 0

연속해서 나타나는 패턴의 길이는 1 2 4 1 2 이렇게 구할 수 있다. 나뉘는 구간은 그림에 나타난다

 

나뉘는 구간이 3개가 있다면 두번째 구간의 시작 상태(0, 1)는 첫번째 구간의 마지막 전구 상태와 같을 수 밖에 없고, 두번째 구간의 마지막 상태는 세번째 구간의 첫번째 전구 상태와 같을 수 밖에 없다.

따라서 두 번째 구간을 모두 뒤집는다고 하면 3개의 구간은 서로 교대패턴으로 이어질 수 밖에없다.

 

단 한번만 뒤집을 수 있기 때문에 하나의 패턴 구간만 선택해서 뒤집을 수 밖에 없다.

해당 구간은 연속된 3개의 구간 중 가운데 구간이 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N;
int arr[100001];
vector<int> chain;
 
void input(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
}
 
void solve(){
    int prev = arr[0], cnt = 1;
    for(int i = 1; i < N; i++){
        if(arr[i] == prev){
            chain.push_back(cnt);
            cnt = 1;
        }
        else{
            cnt++;
            prev = arr[i];
        }
    }
    chain.push_back(cnt);
    
    int ans = 0;
    if(chain.size() == 1) ans = chain[0];
    else if(chain.size() == 2) ans = chain[0] + chain[1];
    else{
        for(int i = 0; i < chain.size()-2; i++){
            ans = max(ans, chain[i] + chain[i+1] + chain[i+2]);
        }
    }
    
    cout << ans << "\n";
}
 
int main(){
    input();
    solve();
    
    return 0;
}