[알고리즘] BOJ 2138 전구와 스위치 #Python

[BOJ] 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을 출력한다

---

📍 풀이

📌 문제 풀이

해당 문제를 해결하는데 가장 중요한 키 포인트는 2가지이다.

1. 첫 번째에 해당하는 전구의 상태를 변화시킬 것인가 아닐 것인가.
2. 왼쪽부터 순차적으로 전구의 상태를 변화시키는 작업을 수행할 때 다시는 접근할 수 없는 왼쪽 전구를 기준으로 전구의 상태를 변화시켜야 한다.

두 조건만을 고려하여 코드를 작성하면 문제를 해결할 수 있다.

✍ 코드

from sys import stdin, maxsize
from copy import deepcopy

MID = "mid"
END = "end"

def solution(N, default, target):
    answer = maxsize
    # case1 : 첫 번째 전구의 상태를 변화시키지 않는 경우
    # case2 : 첫 번재 전구의 상태를 변화시키는 경우
    def createCase(default):
        case1 = default
        case2 = deepcopy(case1)
        case2[0], case2[1] = abs(case2[0]-1), abs(case2[1]-1)
        return case1, case2
    
    # idx 위치의 스위치를 누르는 경우
    def switchOn(cases, idx, type):
    	# 마지막 위치의 스위치가 아닌 경우
        if type == MID:
            cases[idx-1],  cases[idx], cases[idx+1] = abs(cases[idx-1]-1),  abs(cases[idx]-1), abs(cases[idx+1]-1)
        # 마지막 위치의 스위치인 경우
        elif type == END:
            cases[idx-1],  cases[idx] = abs(cases[idx-1]-1),  abs(cases[idx]-1)

    case1, case2 = createCase(default)
    cnt1, cnt2 = 0, 1 # 스위치 작동 횟수

    for idx in range(1,N):
    	# 마지막 스위치가 아닌 경우
        if idx != N-1: 
        	# 왼쪽 기즌 전구의 값이 다른 경우
            if target[idx-1] != case1[idx-1]:
                switchOn(case1, idx, MID)
                cnt1 += 1
            # 왼쪽 기즌 전구의 값이 다른 경우
            if target[idx-1] != case2[idx-1]:
                switchOn(case2, idx, MID)
                cnt2 += 1
        # 마지막 스위치인 경우
        else: 
        	# 왼쪽 기즌 전구의 값이 다른 경우
            if target[idx-1] != case1[idx-1]:
                switchOn(case1, idx, END)
                cnt1 += 1
            # 왼쪽 기즌 전구의 값이 다른 경우
            if target[idx-1] != case2[idx-1]:
                switchOn(case2, idx, END)
                cnt2 += 1

    if int(target[-1]) == case1[-1]:
        answer = cnt1
    if int(target[-1]) == case2[-1]:
        answer = min(answer, cnt2)

    return answer if answer != maxsize else -1

#input
N = int(stdin.readline())
default = list(map(int,list(stdin.readline().strip())))
target = list(map(int,list(stdin.readline().strip())))

# result
result = solution(N, default, target)
print(result)