백준 2138 : 전구와 스위치 ( Python )

문제 링크

📌 사용 알고리즘 : greedy , dynamic programming

1차원 배열 형태의 전구가 있을때 스위치를 적절하게 끄면서 원하는 형태로 만들기 위한 최소값을 구하는 문제입니다.

이때 스위치는 i-1,i,i+1 번째가 동시에 반전되고 1번째와 N번째 스위치를 누르면 1,2 그리고 N-1,N 번째 전구가 반전됩니다.

일단 보자말자 dp 라고 생각했습니다.

몇번 시뮬레이션을 돌리다 보면 스위치를 누르는 순서는 결과에 영향을 끼치지 않습니다.
즉 이전 상태에 영향을 끼지치 않기 때문에 이전값을 활용할 수 있습니다.

만약에 i 번째 전구가 달라서 반전을 시켜야한다면 i-2 번째 전구는 신경을 쓸 필요가 없습니다.

다만 한가지 문제가 있습니다.

첫번째 전구를 누르냐 누르지 않냐에 따라 결과에 영향을 미치게 됩니다.
때로는 첫번째 전구를 누르면 원하는 형태가 만들어지지 않을 때도 있습니다.

이를 어떻게 해결할지 고민을 좀 했는데 N의 범위가 작기 때문에 첫번째 전구를 눌렀을때와 누르지 않았을때 두가지 모두 최소값을 구해주면 되었습니다.

따라서 i-1 번째 전구가 반전이 일어나야 한다면 i-1,i,i+1 번째 전구를 반전 시키면됩니다.
이때 인덱스는 2부터 시작하면 됩니다.

시간복잡도는 O(N) 입니다.

다만 N 이 2일때는 예외처리를 해주어야 합니다.

📌 배열의 복사에 관해서

파이썬에서 배열을 복사할때 주로 copy.deepcopy 를 씁니다.

하지만 배열의 크기가 클때는 slicing 를 통한 복사가 훨씬 더 빠릅니다.

newList = copy.deepcopy(list)
newList = [ i for i in list]

1차원 배열은 위처럼 복사하면 됩니다.

newList = [ i[:] for i in list ]

2차원 배열일 경우에는 위처럼 복사하면 됩니다.

속도의 차이가 발생하는 이유에 대해 궁금하다면 python copy 공식문서 을 보거나 직접 찾아보는것을 추천합니다.

실제 python copy 구현코드 를 보면 설명란에 deepcopy 는 재귀적으로 복사하고 because deep copy copies *everything* it may copy too much, e.g.administrative data structures that should be shared even between copies 라는 문구로 보아서 오래걸리는것 같습니다.

📌 코드

import sys,math,heapq
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]


def switch(bit , target , value):
    for i in range(1, N):
        if bit[i - 1] != target[i - 1]:
            if i != N - 1:
                bit[i - 1] ^= 1
                bit[i] ^= 1
                bit[i + 1] ^= 1
            else:
                bit[i - 1] ^= 1
                bit[i] ^= 1
            value += 1
    if bit==target:
        return value
    else:
        return int(1e9)

N=I()
first=list(map(str,input().rstrip()))
target=list(map(str,input().rstrip()))

for i in range(N):
    first[i] = int(first[i])
    target[i] = int(target[i])

ans = int(1e9)
second = [ _ for _ in first]
second[0]^=1 ; second[1]^=1

if N==2:
    if first == target:
        print(0)
    elif abs(sum(first)-sum(target))==2:
        print(1)
    else:
        print(-1)
else:
    ans = min(ans , switch(first , target , 0))
    ans = min(ans , switch(second , target , 1))
    if ans==int(1e9):
        print(-1)
    else:
        print(ans)