[백준] 2138번: 전구와 스위치(Python, 그리디)

문제

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

2138번: 전구와 스위치

풀이

(2번~ n번)

모든 전구는 i번째를 눌렀을때 i-1번째의 전구 상태를 마지막으로 결정한다.

i번째가 누를지 말지에 따라 i-1번째의 전구 상태가 정해지고 뒤로 가면 i-1번째 전구는 바뀌지 않는다.

그러므로 i번째의 전구를 누를지말지는 i-1번째의 상태와 목표 전구의 상태를 비교하며 결정한다.

(1번 전구 설정하기)

그럼 초기값인 0번째의 전구를 누를지 말지 결정하는것만 예외를 두면 된다.

0번째 전구를 누르면 110

0번째 전구를 안누르면 000

이때 이제 for i in range(1, n) 까지 진행하면서 i-1번의 전구가 목표 전구와 다르면 i번째 스위치를 눌러준다. (왜냐하면 이제 i-1번째의 전구는 i번 전구를 지나가면 변경될 기회가 없기 때문)

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

n = int(input())
origin = map(int, input().rstrip())
goal = list(map(bool, map(int, input().rstrip())))

# 0번째 눌렀을때
first1 = list(map(bool, deepcopy(origin)))
first2 = list(map(bool, deepcopy(origin)))

first1[0] = not first1[0]
first1[1] = not first1[1]

coord = [(first1, 1), (first2, 0)] # 0번째 스위치가 눌린 경우와 안눌린 경우 담기
answer = 10 ** 6

if first2 == goal:
    print(0)
else:
    for element in coord:
        item, cnt = element

        for i in range(1, n):
            if item == goal:
                break

            if item[i-1] == goal[i-1]:
                continue

            if item[i-1] != goal[i-1]:
                if i == n - 1:
                    item[i - 1], item[i] = not item[i-1], not item[i]
                else:
                    item[i-1], item[i], item[i+1] = not item[i-1], not item[i], not item[i + 1]
                cnt += 1

        if item == goal and cnt < answer:
            answer = cnt

    if answer == 10**6:
        answer = -1
    print(answer)