[백준/Python(파이썬)] 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을 출력한다.

 

그리디 문제! 시작할 때 스위치를 누른다 / 안누른다 두 가지 분기로 나눠서 값을 구한다

스위치를 누르면 앞 뒤 전구 상태가 변하기 때문에 앞에 있는 전구 상태를 만들고자 하는 전구의 상태와 비교해서 스위치 누를지 결정함

 

[소스코드]

n = int(input())
c = list(map(int,input().rstrip("\n")))
want = list(map(int,input().rstrip("\n")))

def change(num):
    if num == 0:
        num = 1
    else:
        num = 0
    return num

def switch(c, cnt):
    count = cnt
    if count == 1:
        c[0] = change(c[0])
        c[1] = change(c[1])
    for i in range(1, n):
        if c[i-1] != want[i-1]:
            count += 1
            c[i-1] = change(c[i-1])
            c[i] = change(c[i])
            if i != n-1:
                c[i+1] = change(c[i+1])
    if c == want:
        return count
    else:
        return -1

res1 = switch(c[:], 0)
res2 = switch(c[:], 1)
if res1 >= 0 and res2 >= 0:
    print(min(res1, res2))
elif res1>=0 and res2 < 0:
    print(res1)
elif res1 <0 and res2 >= 0:
    print(res2)
else:
    print(-1)

github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_2138.py

jisun1125/algorithm-problem-solving

https://www.acmicpc.net/problem/2138 

2138번: 전구와 스위치