[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가지이다.
두 조건만을 고려하여 코드를 작성하면 문제를 해결할 수 있다.
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)