백준 5527 전구 장식 python

문제

5527번: 전구 장식 (acmicpc.net)

5527번: 전구 장식

아이디어

길이 N의

ref1 = 01010101....

ref2 = 10101010.... 형식의 전구를 생각해보자.

우리들이 전구를 조작했을 때 max(ref1와 가장 길게 매칭되는 경우, ref2와 가장 길게 매칭되는 경우)가 우리가 원하는 것이다.

각 구간은 ref1과 매칭되거나 그것이 아니라면 ref2와 매칭된다.

그 경우중 ref1와 가장 길게 매칭되는 경우를 생각해보자.

전구를 조작하면 원래 ref1와 매칭이 안된 구간(ref2와 매칭된 구간)은 매칭될 것이다.

그럼 우리는 ref1과 매칭된 구간의 길이와 그것의 앞뒤에 붙어있는 ref2와 매칭된 구간의 길이를 보면 될 것이다.

또한 ref2와 매칭된 구간의 길이와 그것의 앞뒤에 붙어있는 ref1와 매칭된 구간의 길이를 보면 된다.

좀 더 봐야하지만 굵은 글씨를 보며 더 생각해보자.

 

 

풀이

1. ref1과 ref2를 만들어주자

2. 우리들은 구간의 길이를 볼 것이다.

따라서 미리 만들어주자.

누적합과 비슷하게 특정 인덱스에 대해 이 인덱스까지 ref와 얼만큼 매칭된지를 알 수 있는 데이터를 만들어줘야한다.

ref1과 얼마나 매칭됐는지를 구하려면

N = int(input())
A = list(map(int,input().split()))
dp = [0] * N
for i in range(N):
	if ref1[i] == A[i]:
    	dp[i] = dp[i-1] + 1

대충 이렇게 만들어주면 된다.

ref2에 대해서도 똑같이 만들어주면 된다.

하지만 만든 dp는 dp[i] = k 라면 i~ i-k+1까지 ref1와 매칭된다는 의미이다.

우리들은 i+1부터 얼마나 ref2와 매칭됐는지 알고 싶다.

지금은 저렇게 붙어있는걸 쉽게 계산할 순 없다.

따라서 간단하게 그냥 만들어보자. 역방향으로 만들어주면 된다.

for i in range(N-1,-1,-1):
	if ref[i] == A[i]:
    	dp[i] = dp[i+1] + 1

(들여쓰기가 안됩니다ㅠㅠ그냥 로직만 담은 코드이므로 패스)

지금 우리는

1.dp1[i] = k : ref1과 i~i-k+1만큼 매칭됨

2.dp2[i] = k: ref2와 i~i-k+1 만큼 매칭됨

3.dp3[i] = k: ref1과 i~i+k-1 만큼 매칭됨

4.dp4[i] = k: ref2와 i~i+k-1 만큼 매칭됨

를 만들어줬다.

3. 정답을 구하자

i를 0부터 N-1부터 순회하며

x = dp1[i]

y = dp4[i+1]

을 보자.

단순히 x+y만 하기에는 아이디어에 굵은 글씨 친 곳을 생각해보면 부족함을 알 수 있다.

여기서 우리는 둘중 어떤 구간([i~i-x+1],[i+1~i+y])에 스위치를 작동시킬지 결정해야한다.

만약 전자에 작동시키면

i~i-x+1은 ref2가 된다.

그 전 ref2와 매칭되는 구간인 dp2[i-x]도 더해줘야한다.

만약 후자에 작동시키면

i+1~i+y는 ref1이 된다.

그 이후 ref1과 매칭되는 구간인 dp3[i+y+1]도 더해줘야한다.

따라서 정답은 max(xi + yi + dp2[i-xi],xi+yi+dp3[i+yi+1]) 이다.

이것은 모든 경우를 커버한다.

그렇게 O(N)에 문제를 풀 수 있다.

 

코드

import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
ref1 = [0]
ref2 = [1]


def convert(x):
    if x == 1:
        return 0
    else:
        return 1


for _ in range(N - 1):
    ref1.append(convert(ref1[-1]))
    ref2.append(convert(ref2[-1]))

dp = [[0] * N for _ in range(4)]
for i in range(N):
    if A[i] == ref1[i]:
        dp[0][i] = (dp[0][i - 1] if i > 0 else 0) + 1  # ref1 정방향
    if A[i] == ref2[i]:
        dp[1][i] = (dp[1][i - 1] if i > 0 else 0) + 1  # ref2 정방향
for i in range(N - 1, -1, -1):
    if A[i] == ref1[i]:
        dp[2][i] = (dp[2][i + 1] if i + 1 < N else 0) + 1  # ref1 역방향
    if A[i] == ref2[i]:
        dp[3][i] = (dp[3][i + 1] if i + 1 < N else 0) + 1  # ref2 역방향
ans = 2
for i in range(N):
    x = dp[0][i]
    y = dp[3][i + 1] if i + 1 < N else 0
    z = dp[2][i + y + 1] if i + y + 1 < N else 0
    w = dp[1][i - x] if i - x >= 0 else 0
    ans = max((ans, w + x + y, z + x + y))
print(ans)