[백준(Baekjoon)] 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을 출력한다.

 

예제 입력 1 

3
000
010

예제 출력 1 

3

 

---

나의 코드

[Python(파이썬)]

def two_bulb(one, two):
    before[one] = 1 - before[one]
    before[two] = 1 - before[two]

def three_bulb(one, two, three):
    before[one] = 1 - before[one]
    before[two] = 1 - before[two]
    before[three] = 1 - before[three]

import sys

input = sys.stdin.readline
n = int(input())
before = [0] + list(map(int, input().strip()))
after = [0] + list(map(int, input().strip()))
n1, n2 = before[:], before[:]

if before == after:  # 시작할 때 같은 경우
    print(0)
else:
    for j in range(2):  # j=0: 1번 스위치 누름, j=1: 1번 스위치 누르지 않음
        before = n1 if j == 0 else n2
        cnt = 0

        if j == 0:  # 1번 스위치 누른 경우
            two_bulb(1, 2)
            cnt += 1

        for i in range(2, n + 1):
            if before[i - 1] != after[i - 1]:
                if i <= n - 1:  # 2~(n-1)번 스위치
                    three_bulb(i - 1, i, i + 1)
                    cnt += 1
                elif i == n:  # n번 스위치
                    two_bulb(i - 1, i)
                    cnt += 1

        if before == after:
            print(cnt)
            break

    if before != after:
        print(-1)

 

---

풀이

처음 '틀렸습니다'가 나온 이유

 

처음 이 문제를 풀 때 예제도 통과하고 10%까지 올라가다가 틀렸습니다가 나오길래 대체 뭐가 문제인가 한참을 고민했다. 그러다 깨닫게 된 치명적 오류,,, n번 스위치를 누르기 위해서 (1~n)스위치를 모두 눌러야하는 것이 아니었다. 

문제에는 n번을 누르기위해서는 (1~n-1)스위치를 모두 눌러야한다라는 어떠한 말도 없었는데 왜 착각을 했는지ㅠㅠ

즉, 3번을 누르기 위해서는 1, 2, 3번 순서대로 눌러야한다고 생각했다. 하지만 1번과 3번만 눌러도 되고 3번 한 개만 눌러도 되는 것이다. 

따라서 문제를 풀 때 왼쪽 첫 전구부터 오른쪽 끝 전구까지 체크하면서 스위치를  누를 것인가 체크해주면 된다. 

 

 

1. 2 ~ n번 스위치 선택 유무

 

위 그림에서 2번 스위치를 누르게 된다면 빨간색 네모칸인 1, 2, 3번 전구의 상태가 변화된다. 

왼쪽에서 오른쪽으로 이동하며 스위치를 누를 지 결정하기 때문에 1번 전구의 상태를 변화시킬 마지막 기회는 2번 스위치이다.

3번 스위치로 이동하게 되면 2, 3, 4번 전구의 상태가 변화하기 때문에 1번은 더이상 변화할 수 없는 것이다.

따라서 스위치를 누를 것인가는 파란색 동그라미 왼쪽에 있는 전구의 상태를 보고 결정해야 한다. 

 

 

 

2. 1번 스위치 선택 유무

 

1번에 말 대로라면 i번 스위치는 i-1 전구를 보고 누를지 말지 결정하는데 1번 스위치는 0번 스위치가 없기 때문에 눌러야할지 말아야할지 결정할 수 없다. 

따라서 1번 스위치를 눌렀을 경우, 누르지 않았을 경우 두가지로 나눠서 생각해야한다.

 

 

 

구현 순서

 

1) 1번 스위치를 누르는 경우, 누르지 않는 경우 두가지로 나눈다. 
2) 1번 스위치를 누른 경우 
2-1) i-1번 전구를 확인하고 2~n번 전구까지 이동하며 누를지 말지 결정한다. 
2-2) n번 스위치 선택 여부까지 결정 한 후 만들고자 하는 상태가 되었는지 확인한다. 
2-3) 만들고자 하는 상태가 되었다면 스위치 누른 횟수를 출력 하고 프로그램 종료
2-4) 만들고자 하는 상태가 되지 않았다면 3)번 으로 계속 진행
3) 1번 스위치를 누르지 않은 경우
3-1) 2번과 똑같이 진행
4) 만들고자 하는 상태가 아직도 되지 않았다면 불가능하므로 -1 출력 

 

---

문제 출처

2138번: 전구와 스위치