[백준 2138 파이썬] 전구와 스위치 그리디 알고리즘

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2≤N≤100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

스위치를 누르면 한칸 앞의 전구와 자기자신과 다음 칸의 전구의 상태가 변한다.

스위치를 누르는 횟수를 최소로 만들기 위해 누르는 스위치의 선택을 맨 앞에서 맨 끝까지 한번 검사하면 된다.

누를지 말지 검사하는 기준은 맨 앞에서 맨 끝까지 한번 검사하기 때문에

한칸 앞의 전구 상태를 비교하여 같으면 누르지 않고 다르면 누르면 된다.

이렇게 문제를 해결하기 위해 우선 맨 처음 스위치를 누를지 말지 경우를 나눠야 한다.

두가지 경우를 zeroClick함수와 zeroNoClick 함수로 나누어

전체 반복문을 순회하고 state와 result가 같은지 비교한다. 같을 경우 count를 반환하고 같지 않을 경우 -1를 반환한다.

이후 두 경우의 return 값인 res1과 res2를 비교하여 출력한다.

 

import sys

def zeroClick(state):
    count=1
    state[0]=int(not state[0])
    state[1] = int(not state[1])
    for i in range(1,n):
        if(state[i-1]!=result[i-1]):
            count+=1
            state[i-1]=int(not state[i-1])
            state[i]=int(not state[i])
            if(i!=n-1):
                state[i+1]=int(not state[i+1])
    if(state==result):
        return count
    else:
        return -1
def zeroNoClick(state):
    count=0
    for i in range(1,n):
        if(state[i-1]!=result[i-1]):
            count+=1
            state[i-1]=int(not state[i-1])
            state[i]=int(not state[i])
            if(i!=n-1):
                state[i+1]=int(not state[i+1])
    if(state==result):
        return count
    else:
        return -1

n = int(sys.stdin.readline().rstrip("\n"))
state = list(map(int,sys.stdin.readline().rstrip("\n")))
result = list(map(int,sys.stdin.readline().rstrip("\n")))
res1 = zeroClick(state[:])
res2 = zeroNoClick(state[:])
if(res1>=0 and res2>=0):
    print(min(res1,res2))
elif(res1>=0 and res2<0):
    print(res1)
elif(res1<0 and res2>=0):
    print(res2)
else:
    print(-1)