[백준] 2138. 전구와 스위치 (파이썬)

cjkangme·2023년 6월 3일

그리디 백준 알고리즘

Algorithm

목록 보기

24/35

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

문제 요약

0이면 꺼진 전구, 1이면 켜진 전구를 의미하는 전구들의 상태 A, B가 주어진다.
i번째 전구 스위치를 누르면, i-1, i, i+1 3개의 인접한 전구의 상태가 바뀐다.
A 상태를 B 상태로 바꾸기 위해 스위치를 최소 몇번 눌러야 하는지 구해야 한다.
바꾸는 것이 불가능할 수 있으며 이 경우 -1을 출력한다.

예제

N = 3
A = 000
B = 010

A의 0번 스위치를 누르면 110 으로 상태가 변한다
A의 1번 스위치를 누르면 001 으로 상태가 변한다.
A의 2번 스위치를 누르면 010 으로 상태가 변한다.

총 3번 스위치를 눌렀고, A 상태에서 B 상태로 변경되었으므로 답은 3이다. (3보다 적게 누를 수 없음)

풀이

1. 전구를 누르는 순서는 상관이 없다.

가령 위의 예제에서 1->0->2 순으로 누르거나, 2->1->0으로 눌러도 똑같은 상태가 된다.

즉 누르는 순서를 신경쓸 필요 없이 0번 스위치부터 N-1번 스위치까지 순차적으로 돌면서 해당 스위치를 눌러도 될지 말지만 결정하면 된다.

2. 순차적으로 탐색한다면 i번째 스위치가 i-1번째 전구의 상태를 결정할 마지막 스위치이다.

다시 예제를 보자

A = 000
B = 010

0번째 스위치를 누른 경우

0번째 스위치를 누른 경우 A는 110이다.
1번째 스위치에서는 반드시 스위치를 눌러야한다. 왜냐하면 A와 B가 같기 위해서는 A[0] = B[0] = 0이어야 하는데, 현재 110 상태에서 스위치를 누르지 않고 지나가면 A[0]이 영원히 1이 되기 때문이다.
1번째 스위치를 눌렀다면 A는 001이다.
2번째 스위치 역시 반드시 스위치를 눌러야한다. A[1] = B[1] = 1이 되어야 하는데 현재 A[1] = 0이기 때문이다.

0번째 스위치를 누르지 않은 경우

0번째 스위치를 누른 경우 A는 000이다.
1번째 스위치에서는 반드시 스위치를 누르지 않아야 한다. 1번 스위치를 누르면 A[0] 값이 영원히 1이 되기 때문이다. 여전히 A의 상태는 000이다.
반대로 2번째 스위치는 반드시 눌러야한다. A[1] 값이 1이 되어야 하기 때문이다. 그러나 2번째 스위치를 누르면 A의 상태는 011이 되어 A != B이다.

결론

즉 0번째 스위치만 누를지 말지만이 경우의 수이며, 나머지는 모두 A[i-1], B[i-1] 값에 따라 고정된다.
이를 코드로 구현하면 된다.

코드

import sys

input = sys.stdin.readline

# 스위치를 눌렀을 때 상태 변경을 해주는 함수
def reverse(bulbs, count):
    for i in range(1, N-1):
        if bulbs[i-1] != target[i-1]:
            count += 1
            for j in range(i-1, i+2):
                bulbs[j] = not bulbs[j]
    # 마지막 전구만 따로 처리
    if bulbs[N-1] != target[N-1]:
        count += 1
        bulbs[N-2] = not bulbs[N-2]
        bulbs[N-1] = not bulbs[N-1]
    if bulbs == target:
        return count
    else:
        return -1


N = int(input())

# not을 이용해 간편하게 처리하고 싶어서 0:False, 1:True의 bool 값으로 바꾸었다.
off = list(map(bool, map(int, input().rstrip())))

# 0번째 스위치를 누른 상태를 저장하는 리스트
on = off.copy()
on[0] = not on[0]
on[1] = not on[1]

target = list(map(bool, map(int, input().rstrip())))

# 처음부터 상태가 같은 경우 스위치를 눌러줄 필요가 없으니 0 출력
if off == target:
    print(0)
else:
    # 0번째 전구를 안눌렀을 때
    count = reverse(off, 0)
    if count != -1:
        print(count)
    else:
        # 0번째 전구를 눌렀을 때
        count = reverse(on, 1)
        print(count if count else -1)