[Baekjoon] 2138번 : 전구와 스위치

1. 문제

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을 출력한다.

// 예제 입력 1 
3
000
010

// 예제 출력 1 
3

2. 핵심 아이디어

3. Python 문제풀이

import sys
import copy
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().rstrip()))
b = list(map(int, input().rstrip()))

r1 = copy.deepcopy(a)
r2 = copy.deepcopy(a)

def two_flip(i, j) :
  a[i] = 1 - a[i]
  a[j] = 1 - a[j]

def three_flip(i, j, k) :
  a[i] = 1 - a[i]
  a[j] = 1 - a[j]
  a[k] = 1 - a[k]

for i in range(2) :
  a = r1 if i == 0 else r2
  cnt = 0
  for j in range(n):
    if j == 0:
      if i == 0 and a != b :
        cnt += 1
        two_flip(j, j+1)

    elif 1 <= j <= n-2 :
      if a[j-1] != b[j-1] :
        cnt += 1
        three_flip(j-1, j, j+1)

    elif j == n-1 :
      if a[j-1] != b[j-1] :
        cnt += 1
        two_flip(j-1, j)

  if a == b :
    print(cnt)
    break

if a != b:
  print(-1)

4. Java 문제풀이