[5527] 전구 장식

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

처음에 예제를 보고

같은 전구가 반복되는 pos부터

같은 전구가 또 반복되는 pos -1까지 반전시키면 된다고 생각했습니다.

예제의

1 1 0 0 1 0 1 1 1 0

의 예제에서

처음 1 1(pos 0, 1)이 반복됩니다. 

그래서 pos = 1 부터 그 다음에 0 0 이 반복되기 때문에 pos - 1까지의 구간을 반전시키면

1 0 1 0 1 0 1 1 1 0

7이 됩니다.

그 다음 다시 원상 복귀!

1 1 0 0 1 0 1 1 1 0에서

0 0 구간 (위에서 찾은 pos 값 즉.. 3!!!!! 인덱스를 말하는 것)

3부터 시작해서

또 반복되는 구간은

1 1 1

즉 인덱스(pos) 7입니다. 그럼 pos - 1까지 반전을 시켜야하므로

1 1 0 1 0 1 0 1 1 0

7이 됩니다.

마지막으로

1 1 1 구간에서 반복이 연속되므로  1 0 1을 바꿔주는 경우가 있습니다.

1 1 0 0 1 0 1 0 1 0

이것또한 7입니다.

즉 정답은 7입니다!!!!!!!

근데... 이렇게 푸니까 시간 초과..ㅠㅠㅠㅠㅠ

반전시키는 구간 길이가 n이면 n만큼의 시간이 걸릴테고..

구간을 찾는 것도 시간이 걸리고...

여러가지 이유로 시간이 초과됩니다...

n의 시간으로 해결할 수 있어야 할 것 같은데 방법이 잘 떠오르지 않았습니다.

문제의 해결 방법은

전구를 세 구간으로 나누는 것입니다.

이게 무슨 말이냐면

반전 시키는 구간을 O

아닌 구간을 X로 치면

O X X

X O X

X X O

로 구간을 나누면 된다는 말입니다.

구간을 나누는 기준은 같은 전구가 반복되는 pos입니다.

1 1 0 0 1 0 1 1 1 0

이 예제에서는 위에서 설명한 구간이겠지요.

이렇게 해서

배열에 같은 전구가 나올 때 까지의 번갈아가는 패턴의 값을 저장합니다.!

a[0] = 1;(인덱스 0에서 0구간)

a[1] = 2;(인덱스 1에서 2구간)

a[2] = 4;(인덱스 3에서 6구간)

a[3] = 1;(인덱스 7에서 7구간)

a[4] = 2;(인덱스 8에서 9구간)

이렇게 다섯개의 구간이 생성됩니다.

이 5개의 구간 중 연속된 3개를 더하면 최대 번갈아가는 패턴의 값이 나오겠지요!

아래는 정답 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
int a[MAX_SIZE];
int n;
 
int main() {
 
    scanf("%d", &n);
 
    int before = -1;
    int pos = 1;
 
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        
        if (before == t) pos++;
        
        a[pos]++;
        before = t;
    }
 
    int ret = 0;
    for (int i = 1; i <= pos; i++) {
        ret = max(ret, a[i - 1] + a[i] + a[i + 1]);
    }
 
    printf("%d", ret);
 
    return 0;
}
 

시간초과 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
bool a[MAX_SIZE];
int n;
 
int cnt(int start, int end) {
    int before = -1;
    int ret = 0;
    int tmp = 0;
 
    bool flag = 0;
    for (int i = 0; i < n; i++) {
        if (start <= i && i <= end) {
            a[i] = !a[i];
            flag = 1;
        }
        if (before != a[i]) tmp++;
        else ret = max(ret, tmp), tmp = 1;
 
        before = a[i];
 
        if (flag) {
            flag = 0;
            a[i] = !a[i];
        }
    }
 
    return ret;
}
 
int f(int pos, int before) {
    int i;
 
    for (i = pos + 1; i < n; i++) {
        if (before == a[i]) {
            break;
        }
 
        before = a[i];
    }
 
    return cnt(pos, i - 1);
}
 
int main() {
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    
    int before = -1;
    int ret = cnt(-1, -1);
 
    for (int i = 0; i < n; i++) {
        if (before == a[i]) {
            ret = max(ret, f(i, a[i]));
        }
 
        before = a[i];
    }
 
    printf("%d", ret);
 
    return 0;
}