[백준 2138 🥇] 전구와 스위치

문제

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

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

입력

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

출력

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

문제 풀이

import sys

n=int(sys.stdin.readline())
start=list(map(int, sys.stdin.readline().strip()))
goal=list(map(int, sys.stdin.readline().strip()))

ans=[]
# 0번 스위치를 누른 경우
pushzero=1
pushzero_start=start.copy()
pushzero_start[0]=1-pushzero_start[0]
pushzero_start[1]=1-pushzero_start[1]
for i in range(1,n):
    if pushzero_start[i-1]!=goal[i-1]:
        pushzero+=1
        # i번 스위치 눌러야 함
        for t in (i-1, i, i+1):
            if 0<=t<n:
                pushzero_start[t]=1-pushzero_start[t]
if pushzero_start==goal:
    ans.append(pushzero)

# 0번 스위치 안누른 경우
notpushzero=0
for i in range(1,n):
    if start[i-1]!=goal[i-1]:
        notpushzero+=1
        for t in (i-1,i,i+1):
            if 0<=t<n:
                start[t]=1-start[t]
if start==goal:
    ans.append(notpushzero)

if ans:
    print(min(ans))
else:
    print(-1)

이 문제는 풀이가 떠오르지 않아서 아래 링크를 참고했다...!

https://staticvoidlife.tistory.com/143

[그리디 알고리즘] 전구와 스위치

위 블로그의 풀이대로 이해하며 풀었다. 이런 생각은 어느정도 경지에 올라야 생각해낼 수 있는지 신기했다. 분발하자!

추가적으로 

1. 버튼을 누르는 순서는 상관이 없다.

예를 들어, 000을 예로 들면 1번을 누르고 2번을 누르는 경우 000 -> 111 -> 100이고,

2번을 누르고 1번을 누르는 경우 000 -> 011 -> 100으로 결과적으로 100 동일한 값이 된다.

 

2. 최소한 눌러야 한다는 것은 각 스위치를 최대 1번까지 눌러야 한다는 것이다.

그 이유는 2번 누르는 경우 아예 누르지 않는 상태와 동일하고, 3번 누르는 경우 1번 누르는 상태와 동일하고, 4번을 누르는 경우 다시 아예 누르지 않는 상태와 동일해진다. 이렇게 누르는 결과가 반복되기 때문에 0번 또는 1번 눌러야 버튼을 최소화해서 누를 수 있다.