[백준] 2138 전구와 스위치 (파이썬)

골드 Ⅴ

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

2138번: 전구와 스위치

 

📄 문제

• N개의 스위치와 N개의 전구가 있다.
• 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다.
• i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다.
• 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다.
• 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고,
• N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

 

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

---

💡 아이디어

• 앞쪽 전구의 스위치 부터 순서대로 누를지 말지를 결정하면서 마지막 스위치에서 원하는 상태가 됐는지 확인한다.
• 맨 앞의 전구의 상태를 고정한다. (on / off)
• 맨 앞 전구의 스위치를 누르지 않고 시작하면 횟수는 0 으로 시작한다.
• 맨 앞 전구의 스위치를 누르고 시작하면 횟수는 1로 시작한다.
• 두번째 전구의 스위치부터 바로 앞 전구의 상태를 확인하며 스위치를 누를 지 말지 결정한다.
  • 원하는 전구 상태와 비교하여 상태 변화가 필요하면 스위치를 누른다.

• 상태 변화가 필요하면 스위치를 누르고 횟수도 올려준다.
• 마지막 스위치의 상태를 결정하고 변화된 상태가 원하는 상태와 같은지 비교한다.
• 원하는 상태가 되면 횟수를 반환한다.

 

 

각각의 스위치가 영향을 주는 전구를 표현하면 아래와 같다.

 

전구
영향	↑↗	↖↑↗	↖↑↗	↖↑
스위치 (인덱스)	0	1	2	3

 

만약, 0번 스위치의 상태(누른다/누르지 않는다)가 이미 정해져 있다면 각 스위치가 영향을 주는 전구는 아래와 같이 달라진다.

 

전구	켜짐 or 꺼짐
영향	먼저 선택	↖↑↗	↖↑↗	↖↑
스위치 (인덱스)	0	1	2	3

 

0번 스위치의 상태가 정해졌으므로, 0번 전구에 영향을 줄 수 있는 스위치는 1번 스위치 뿐이다.

따라서, 원하는 상태와 0번 전구의 상태가 서로 다르면 반드시 1번 스위치를 눌러야한다.

 

0번 전구의 상태에 따라 1번 스위치를 누를지 말지 정하면,  1번 전구 상태에 영향을 주는 것은 2번 스위치 밖에 없게된다.

 

이런식으로 반복하여 진행했을 때, 마지막 스위치를 작동 시킨 상태와 만들고자 하는 상태가 같으면 가능하고 다르다면 불가능한 것을 의미한다.

 

---

이 문제는 최대 100000개의 스위치가 존재한다.

따라서, Brute Force를 활용하여 100000의 스위치를 모두 누른다/누르지 않는다로  확인하면 시간초과가 발생한다. (시간 복잡도 =  2^100000)

 

📝 문제 풀이 (Code)

최종코드 ( 실행시간80 ms, 메모리33604 KB )

 slicing을 활용한 깊은 복사

import sys
input = sys.stdin.readline

def switch(bulb, cnt):

    for i in range(1, n):
        # 0번 스위치를 고정하면
        # 0번을 변화 시킬수 있는건 1번 스위치 뿐이다.
        if bulb[i - 1] != result[i - 1]:
            cnt += 1
            # 스위치 누르기
            bulb[i-1] = onOff[bulb[i-1]]
            bulb[i] = onOff[bulb[i]]
            if i < n-1:
                bulb[i+1] = onOff[bulb[i+1]]

    if bulb[-1] == result[-1]:
        return cnt
    return 100001


n = int(input().rstrip())
state = list(input().rstrip())
result = list(input().rstrip())

onOff = {'1': '0', '0': '1'}
# 첫번째 스위치 안누르고 시작
case1 = state[:]
# 첫번째 스위치를 누르고 시작
state[0] = onOff[state[0]]
state[1] = onOff[state[1]]

ans = min(switch(case1, 0), switch(state, 1))
if ans == 100001:
    print(-1)
else:
    print(ans)

 

deepcopy()를 활용한 코드 ( 실행시간 128 ms, 메모리 33976 KB )

copy 모듈의 deepcopy() 메소드를 활용한 깊은 복사

처리속도는 리스트 슬라이싱이 가장 빠르고 copy 모듈의 deepcopy() 메소드가 가장 느리다.

 

최종 코드와 차이점

• from copy import deepcopy를 사용했다.
• state[:] 대신 deepcopy(state)를 사용했다.

from copy import deepcopy
import sys
input = sys.stdin.readline

def switch(bulb, cnt):

    for i in range(1, n):
        # 0번 스위치를 고정하면
        # 0번을 변화 시킬수 있는건 1번 스위치 뿐이다.
        if bulb[i - 1] != result[i - 1]:
            cnt += 1
            # 스위치 누르기
            bulb[i-1] = onOff[bulb[i-1]]
            bulb[i] = onOff[bulb[i]]
            if i < n-1:
                bulb[i+1] = onOff[bulb[i+1]]

    if bulb[-1] == result[-1]:
        return cnt
    return 100001


n = int(input().rstrip())
state = list(input().rstrip())
result = list(input().rstrip())

onOff = {'1': '0', '0': '1'}
# 첫번째 스위치 안누르고 시작
case1 = deepcopy(state)
# 첫번째 스위치를 누르고 시작
state[0] = onOff[state[0]]
state[1] = onOff[state[1]]

ans = min(switch(case1, 0), switch(state, 1))
if ans == 100001:
    print(-1)
else:
    print(ans)

 

처음 코드 ( 실행시간 136 ms, 메모리 33996 KB )

from copy import deepcopy
import sys
input = sys.stdin.readline

def switch(idx, bulb):

    if idx == 0:
        arr = [0, 1]
    elif idx == n-1:
        arr = [n-2, n-1]
    else:
        arr = [idx-1, idx, idx+1]

    for i in arr:
        if bulb[i] == '0':
            bulb[i] = '1'
        else:
            bulb[i] = '0'

    return bulb


def change(bulb, cnt):

    for k in range(1, n):
        # 0번 스위치를 고정하면
        # 0번을 변화 시킬수 있는건 1번 스위치 뿐이다.
        if bulb[k - 1] != result[k - 1]:
            bulb = switch(k, bulb)
            cnt += 1

    if bulb[-1] == result[-1]:
        return cnt
    return 100001


n = int(input().rstrip())
state = list(input().rstrip())
result = list(input().rstrip())
# 첫번째 스위치 안누르고 시작
case1 = deepcopy(state)
# 첫번째 스위치를 누르고 시작
case2 = switch(0, state)

ans = min(change(case1, 0), change(case2, 1))
if ans == 100001:
    print(-1)
else:
    print(ans)

---

참고자료

https://staticvoidlife.tistory.com/143