(python) 백준 #2138 - [G5] 전구와 스위치 : 그리디

2138번: 전구와 스위치

 

스위치를 누르는 순서는 상관 없다

고로 처음부터 끝까지 한번 탐색하면 된다.

 

모든 스위치는 누르거나 누르지 않거나 둘 중 하나

두번 누르면 안누른것과 같다. 두번 이상 누르는 경우를 고려할 필요가 없다.

 

누를지 말지 어떻게 결정할까

n번 전구는 n-1, n, n+1번 스위치에만 영향을 받는다. 즉 앞에서 뒤로 순차적으로 탐색할때, n+1번 스위치가 n번 전구에 마지막으로 영향을 줄 수 있는 스위치이다.

스위치의 바로 앞 전구의 상태를 기준으로 누를지 말지를 결정하도록 한다. 이렇게 마지막 스위치까지 확인한 후 첫 스위치는 기준이 없기 때문에 누르거나 누르지 않거나 두가지를 모두 확인해야한다.

 

해답은 유일할까?

해답은 없는 경우도 있고, 2가지가 있는 경우도 있다.

첫번째 스위치를 눌렀을때, 누르지 않았을때 모두 해답이 존재할 수 있다.

00000 -> 11011

1. 1번, 5번 스위치 작동

2. 2번, 4번 스위치 작동

두가지 방법이 가능하다.

단 추측컨데 두가지 방법이 가능한 경우 두 방법의 스위치 누르는 횟수는 동일하다.

 

코드

import sys
from copy import deepcopy


def solution(input) :
    N = int(input().rstrip())
    S = input().rstrip()
    T = input().rstrip()
    
    is_same = [S[i] == T[i] for i in range(N)] # 매번 비교하지말고 모두 비교해서 배열 하나를 만들기
    
    def check(same, c) :
        count = c
        for i in range(1,N) :
            if same[i-1] : # 이전 전구가 일치하면 스킵
                continue
            else : # 이전 전구가 다르면 스위칭
                same[i] = not same[i]
                try : same[i+1] = not same[i+1]
                except : pass
                count += 1

        return count if same[-1] else -1
    
    # 1번 스위치를 누르지 않은 경우
    count = check(deepcopy(is_same), 0)

    if count != -1 : # 여기서 해답이 나왔으면 출력하고 끝내기
        print(count)
        return
        
    # 위에서 해답이 나오지 않으면
    # 1번 스위치를 누른 경우
    same = deepcopy(is_same)
    same[0] = not same[0]
    same[1] = not same[1]
    count = check(same, 1)

    print(count)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac