220519 - 전구와 스위치

◾ 전구와 스위치 : 백준 2138번

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

문제

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

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

---

입력

• 첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다.
• 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다.
• 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.
  • 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

• 첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

입출력 예

Input	Output
3 000 010	3

---

◾ 풀이

1. 해설

• 최소 횟수로 변경하기 위해서는 왼쪽 또는 오른쪽부터 차례로 진행하며 지나간 구간은 다시 체크하지 않으면 된다.
  • 그리디 알고리즘 활용
• 첫 번째 인덱스에서 스위치를 조작하는 경우와 두 번째 인덱스부터 스위치를 조작하는 경우 2가지가 있다.
  • 2가지 경우를 모두 확인하고 최소 횟수를 선택한다.

---

2. 프로그램

1. n, origin, target 입력
2. 시작 인덱스 기준으로 2가지 경우 탐색(첫 번째, 두 번째)
3. 현재 인덱스 기준 이전 인덱스의 값이 다를 경우 스위치 조작
   • 단, 첫 인덱스의 경우 첫 인덱스가 다를 경우 스위치 조작
4. target과 동일한 형태라면 횟수를 확인하고 최소값으로 변경

# 코드
def two_change(i, j):
    origin[i] = 1 - origin[i]
    origin[j] = 1 - origin[j]

def three_change(i, j, k):
    origin[i] = 1 - origin[i]
    origin[j] = 1 - origin[j]
    origin[k] = 1 - origin[k]

n = int(input())
origin = list(map(int, input()))
target = list(map(int, input()))

answer1 = []
answer2 = []
for v in origin:
    answer1.append(v)
    answer2.append(v)

min_cnt = 1e10
for i in range(2):
    origin = answer1 if i == 0 else answer2

    cnt = 0
    for j in range(n):
        if j == 0:
            if i == 0 and origin != target:
                cnt += 1
                two_change(j, j+1)
        elif 1 <= j < n-1:
            if origin[j-1] != target[j-1]:
                cnt += 1
                three_change(j-1, j, j+1)
        else:
            if origin[j-1] != target[j-1]:
                cnt += 1
                two_change(j-1, j)

    if origin == target:
        min_cnt = min(min_cnt, cnt)

if min_cnt == 1e10:
    print(-1)
else:
    print(min_cnt)