[그리디] 전구와 스위치(Python)

문제링크

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

2138번: 전구와 스위치

1. 핵심

• 좌우 상태 반전 그리디 유형
  • 같은 곳을 2번 선택하면 선택하지 않는 것과 동일하므로 같은 곳을 2번 선택하지는 않는다.
  • 순차적으로 진행하면서 눌러야하는 위치 판단하는게 유리
  • 첫번째 위치가 선택되는지 안되는지 경우를 나누어서 생각
  • 순차적으로 파악한 후에 마지막 원소가 동일한지 동일하지 않은지 판단한다. 마지막 원소가 같다면 잘 변경된 것이고 마지막 원소가 같지 않다면 불가능한 경우이다.
• XOR 연산
  • S1^□ = S2 양 변에 S2를 XOR 연산을 하면 S1^S2^□ = 0 이다.
  • S1'^□ = 0...S1'을 00000..으로 만드는 □를 찾아야한다.
  • 그래서 우리의 목표는 1 > 0으로 변경시켜야한다. 눌러야할 위치는 1을 0으로 바꿔야하는 부분이다.
• 좌우 상태 반전 그리디 유형은 보통 첫번째 위치를 선택하지 않는데 이 문제에서는 선택할 수 있다. 그러므로 첫번째 위치를 선택한 경우의 상태와 첫번째 위치를 선택하지 않는 상태를 구분해서 생각해야한다.
  • S3는 S1'에서 첫번째 위치를 선택해 S[0]과 S[1]을 반전시킨 상태로 좌우상태 반전을 하도록한다.
• 코드해설
  • 1 > 0으로 변경해야하므로 인덱스 1부터 순차적으로 판단한다. ▷ for i in range(1, n)
  • 1이면 반전시키고 누른 횟수를 가산한다.
    • 좌우반전시킬 때 주의해야할 점은 OutOfIndex가 되지 않도록 주의한다.
  • 마지막 원소로 항상 판단을 하는데 마지막 원소가 0이 아니라면 불가능한 경우이다.
  • simulate(s1)은 첫번째를 누르지 않고 simulate를 했을 때를 의미하고 simulate(s3)은 첫번째를 누르고 simulate한 것을 의미하는데 첫번째를 눌렀으므로 +1을 한다.

 

2. 코드(Python)

n = int(input())
s1 = list(map(int, input()))
s2 = list(map(int, input()))

for i, x in enumerate(s2):
    s1[i] ^= x
# to zero all
s3 = s1.copy()
s3[0] ^= 1
s3[1] ^= 1

inf = int(1e9)

def simulate(s1):
    cnt = 0
    for i in range(1, n):
        if s1[i - 1]:
            cnt += 1
            s1[i - 1] ^= 1
            s1[i] ^= 1
            if i + 1 < n:
                s1[i + 1] ^= 1
    if s1[-1]:
        return inf
    return cnt

ans = min(simulate(s1), simulate(s3) + 1)

if ans == inf:
    print(-1)
else:
    print(ans)