벡준 2138번, 전구와 스위치

문제링크

 

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

2138번: 전구와 스위치

---

 

문제 설명 / 풀이

1. 그리디 문제이므로 최소한의 횟수를 구해야 하므로 왼쪽 첫 전구부터 오른쪽 끝 전구까지 1번씩만 체크하며 뒤집을지 여부를 체크해주면 된다. (왜냐면 이미 왼쪽에서 맞춰놨는데 오른쪽으로 넘어간 후에 또 왼쪽을 볼 필요는 없기 때문에)

-> 전구의 상태를 바꾸면 양옆 전구가 바뀌기 때문에 두번째 전구부터 시작해서 이전 전구의 상태가 희망하는 상태와 같은지 확인하고 다르다면 스위치를 눌러 상태를 변경하자

 

2. 첫번째 전구는 비교 대상이 없으므로, 누르는 경우 누르지 않는 경우 둘 다를 확인하자

 

코드:

n = int(input())
bulb = list(map(int, input()))
target = list(map(int, input()))


def change(A, B):
    L = A[:]
    press = 0
    for i in range(1, n):
        # 이전 전구가 같은 상태면 pass
        if L[i-1] == B[i-1]:
            continue
        # 상태가 다를 경우
        press += 1
        for j in range(i-1, i+2):
            if j<n:
                L[j] = 1 - L[j]
    return press if L == B else 1e9


# 첫번째 전구의 스위치를 누르지 않는 경우
res = change(bulb, target)
# 첫번째 전구의 스위치를 누르는 경우
bulb[0] = 1 - bulb[0]
bulb[1] = 1 - bulb[1]
res = min(res, change(bulb, target) + 1)
print(res if res != 1e9 else -1)