백준 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을 출력한다.

---

풀이

Greedy

이 문제의 핵심은 첫번째 전구의 스위치를 누르는 경우와 안누르는 경우 두개로 나눠서 생각하면 된다.

먼저 안누르는 경우부터 체크한다 (안누르니까 count가 더 적다). 체크하기전에 같은지 확인부터 하고 인덱스 1부터 시작한다.

2번째 전구를 검사할 때 1번째 전구의 값이랑 원하는 전구의 첫번째 값이랑 같은지 확인한다. 여기서 다르면 두번째 전구의 스위치를 눌러준다. 이런식으로 그 전구를 검사하는게 아니라 그 전의 전구를 검사해서 마지막 인덱스까지 검사함.)  loop를 돌때마다 같은지 확인해 주고 같으면 isEnd를 True로 바꿔준다. 

만약에 첫번째 스위치를 안누르는 경우에 같은 경우가 생기지 않으면 첫번째를 누르고 시작하는 경우도 검사한다.

같은 로직으로 검사하고 만약에 경우에 없으면 -1를 출력한다.

 

이 문제는 엄청 여러번 틀렸는데 처음에는 시간을 고려안하고 무식하게 풀어서 시간초과가 났고 틀렸을 때는 검사하는 순서를 잘못해서 틀렸다.

검사하는 순서는 처음에 같은지 확인하고 -> 같지 않다면 마지막 인덱스인지 확인하고 -> 마지막인덱스가 아니면 전의 값을 비교해서 같으면 pass하고 다르면 스위치를 눌러준다.

 

# 2138 전구와 스위치
# Greedy
import sys


def change_OnOFF(value):
    if value == "0":
        value = "1"
    else:
        value = "0"
    return value


def change(n, t):
    if n == 0:
        t[0] = change_OnOFF(t[0])
        t[1] = change_OnOFF(t[1])
    elif n == N - 1:
        t[-1] = change_OnOFF(t[-1])
        t[-2] = change_OnOFF(t[-2])
    else:
        t[n - 1] = change_OnOFF(t[n - 1])
        t[n] = change_OnOFF(t[n])
        t[n + 1] = change_OnOFF(t[n + 1])
    return t


input = sys.stdin.readline
N = int(input())
current = []
result = []
count = 0
current = list(input().strip())
result = list(input().strip())
temp = current[:]
count_list = []
isEnd = False
if current == result:
    print(0)
else:
    # 첫번째 스위치를 안누르는 경우
    for i in range(1, N):
        # 바로 전 값이 다를 경우
        if temp == result:
            print(count)
            isEnd = True
            break
        elif i == N - 1:
            temp = change(i, temp)
            if temp == result:
                count += 1
                print(count)
                isEnd = True
                break
        elif temp[i - 1] != result[i - 1]:
            temp = change(i, temp)
            count += 1
    if isEnd == False:
        temp = current[:]
        temp = change(0, temp)
        count = 1
        # 처음꺼 바꿨는데 맞췄을 경우
        if temp == result:
            print(1)
        else:
            for i in range(1, N):
                if temp == result:
                    print(count)
                    break
                elif i == N - 1:
                    temp = change(i, temp)
                    if temp == result:
                        count += 1
                        print(count)
                        break
                    else:
                        print(-1)
                        break
                elif temp[i - 1] != result[i - 1]:
                    temp = change(i, temp)
                    count += 1