[백준/2138] 전구와 스위치 (Python)

 

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

2138번: 전구와 스위치

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:08:35

 

---

 

문제 설명

 

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

 

입력 예시

 

3
000
010

 

출력 예시

 

3

 

 

---

 

풀이

 

모든 경우의 수를 고려하려면 조합론적인 시간복잡도를 가지게 된다. 최대 N이 10만이므로 당연히 시간 초과를 일으킨다.

 

이 문제의 경우, i번째까지 우리가 만들고자 하는 상태와 현재 상태가 일치한다는 가정 하에 i번째부터의 두 상태를 조율하면 된다는 점을 알 수 있다. 모든 i에 대해 스위치 on/off를 통한 상태 조율을 적용 가능하므로(i번째에 대해 해결하고 나면, i+1번째로 확장하는 식이다), 그리디한 접근을 기대해 볼 수 있다.

 

방식은 간단하다. i번째 스위치로 접근할 수 있는 가장 이전 지역은 i-1이므로, i-1번째가 일치하지 않는다면 i번째 스위치를 눌러 주면 된다. 이를 반복하면 인덱스 1부터 N-1까지의 일치를 보장할 수 있다. 만약 N번째의 두 상태가 일치하지 않는다면 불가능하다는 의미이므로 -1을 출력한다. 그렇지 않으면 총 스위치를 누른 횟수를 출력하면 된다.

 

또한, 위의 탐색은 2번째부터 N번째까지 진행되므로, 1번째 스위치의 작동여부를 검사할 수 없다. 즉 1번째 스위치를 누른 버전과 그렇지 않은 버전으로 나누어 총 2회 탐색하여, 이 탐색값 중 최솟값(둘 다 불가능하다면 -1)을 출력하도록 한다.

 

 

풀이 코드

MAX = float('inf')
N = int(input())
nums = list(input().strip())
target = list(input().strip())
nums = list(map(int, nums))
target = list(map(int, target))

def search(cnt, nums, target) :
  for i in range(1, N) :
    if nums[i-1] != target[i-1] :
      nums[i-1] = 1 - nums[i-1]
      nums[i] = 1 - nums[i]
      if i < N-1 :
        nums[i+1] = 1 - nums[i+1]
      cnt += 1
  return cnt if nums[-1] == target[-1] else MAX

_nums = nums.copy()
for i in range(2) :
  _nums[i] = 1 - _nums[i]

result = MAX
result = min(search(0, nums.copy(), target.copy()), result)
result = min(search(1, _nums, target.copy()), result)

print(result if result < MAX else -1)

풀이 완료!

p.s. 이러한 문제를 2차원으로 확장시켜볼 수도 있을 것이다(꽤 유명한 문제이고, 여러 문제가 있었는데... 블로그에도 정리해 놓았었던 것 같은데 잘 기억나지 않는다. 일단 한번 찾아봐야겠다.