2138. 전구와 스위치

업데이트 시간 : 2023-03-21 01:06:06 +0000

[Gold V] 전구와 스위치 - 2138

성능 요약

메모리: 33604 KB, 시간: 160 ms

분류

그리디 알고리즘

문제 설명

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

💡 Solutions

📄 전구와 스위치.py

N = int(input())
start = list(map(int, input()))
end =  list(map(int, input()))
start_cpy = start[:]
rlt = 2*N
d= (-1,0,1)

x = 0
is_click = False
# cpy는 첫번째 스위치 켜고 출발
for k in d:
    nx = x + k
    if nx < 0 or nx >= N: continue
    start_cpy[nx] = (start_cpy[nx] + 1) % 2
ans = 0
ans_cpy = 1
x += 1


while x < N:

    x_ = x - 1
    if (start[x_] != end[x_]) :
        ans += 1
        for k in d:
            nx = x + k
            if nx < 0 or nx >= N: continue
            start[nx] = (start[nx] + 1) % 2
        pass
    if (start_cpy[x_] != end[x_]) : 
        ans_cpy += 1
        for k in d:
            nx = x + k
            if nx < 0 or nx >= N: continue
            start_cpy[nx] = (start_cpy[nx] + 1) % 2
        pass
        # is_start = False
        # if (start[nx] != end[nx]):
        #     is_click = True
    x += 1

if start == end:
    rlt = min(ans,rlt)
if start_cpy == end:
    rlt = min(ans_cpy,rlt)
if rlt == 2*N:
    rlt = -1
print(rlt)