백준 2138 전구와 스위치 파이썬

www.acmicpc.net/problem/2138

2138번: 전구와 스위치

N = int(input())
state =list(input())
hope = list(input())

def change_zero(light):
    cnt = 1
    light[0] = str(1 - int(light[0]))
    light[1] = str(1 - int(light[1]))
    
    for i in range(1, len(light)):
        if light[i-1] == hope[i-1]:
            continue
        else:
            cnt+=1

            light[i-1] = str(1 - int(light[i - 1]))
            light[i] = str(1 - int(light[i]))
            if i < len(light)-1:
                light[i+1] = str(1 - int(light[i + 1]))
    
    if hope == light:
        return cnt
    
    return 200002

def non_change_zero(light):
    cnt = 0

    for i in range(1, len(light)):
        if light[i-1] == hope[i-1]:
            continue
        else:
            cnt+=1

            light[i-1] = str(1 - int(light[i - 1]))
            light[i] = str(1 - int(light[i]))
            if i < len(light)-1:
                light[i+1] = str(1 - int(light[i + 1]))

    if hope == light:
        return cnt
    
    return 100002

cnt1 = change_zero(state[:])
cnt2 = non_change_zero(state[:])

ans = min(cnt1, cnt2)
if ans == 100002:
    ans = -1
print(ans)

    

이런 유형의 그리디 문제는 이전에 한두번 본적이 있었는데 그때도 못풀었고 이번에도 전혀... 조금도.. 네버 어떤 방법도 규칙도 생각나지 않아 무척 당황스러웠다.

뭐.. 별수 있나. 또 다른 훌륭하신분들의 풀이를 검색해봤다.

다 그렇지만 이 문제 역시 알고나니 너무너무 간단했다.

 

이문제의 핵심은 세가지인데

1. 첫번째 전구를 키는 케이스와 키지 않는 케이스로 나누는것.

2. 한번 지나간 전구는 다시 건드리지 않는것.

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

 

첫번째 핵심인 [첫번째 전구를 키는 케이스와 키지 않는 케이스로 나누는것] 은 첫번째 전구는 비교할 이전 전구가 없기때문에 두가지 경우를 모두 확인하는 것이다.

 

두번째 핵심인 [한번 지나간 전구는 다시 건드리지 않는것]은 한번지나간 전구를 다시 건드린다고 불가능한게 가능해지지도 않고 횟수만 늘어나기 때문이다. 이부분이 그리디로 분류된 이유인듯하다.

 

세번째 핵심인 [전구의 상태를 바꾸면 양옆 전구가 바뀌기 때문에 두번째 전구부터 시작해서 이전 전구의 상태가 희망하는 상태와 같은지 확인하고 다르다면 스위치를 눌러 상태를 변경하는 것] 은 왜 이전 전구의 상태만 비교하냐면 루프가 진행되면서 다음 전구는 결국 비교하게 되기 때문이다.