[python] 2138, 전구와 스위치 : 그리디

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

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 ) 첫번째 전구의 스위치를 누르지 않았을 때 함수 수행

( 2 ) 첫번째 전구의 스위치를 눌렀을 때 함수 수행

( 3 ) 두 함수의 결과를 비교하여 최소횟수 혹은 -1을 출력

 

함수는 반복문을 통해 각 전구를 순서대로 방문하며 스위치를 누를 것인지 누르지 않을 것인지를 결정하고, 스위치를 눌렀다면 그 결과를 반영하여야 한다. 여기서의 포인트는 반복문에서 방문한 현재 전구의 앞에 위치한 전구를 변경시킬 수 있는 기회는 지금이 마지막이라는 사실이다. 내가 만약 두번째 전구에 방문했고, 첫번째 전구가 타겟과 다른 값을 보인다면 무조건 변경시켜줘야 한다. 지금 변경시키지 않으면 앞으로 첫번째 전구는 영영 변경되지 못하게 되고, 그렇게 되면 target과 동일하게 변경시키는 것이 불가능하기 때문이다.

 

그래서, 함수는 다음과 같이 구성된다.

( 1 ) 반복문은 1부터 시작

( 2 ) i - 1번째 전구가 타겟과 다른 값을 보일 때

      →  변경 횟수(count) + 1

      →  (i - 1) ~ (i + 1) 까지의 전구 스위치를 누른 결과 반영 (n보다 작을 때까지)

( 3 ) 만약 타겟과 스위치를 눌러 변경된 결과를 반영한 값이 같으면 count를 return

 

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

# 전구의 스위치를 눌러 상태를 변경하는 함수
def change(bulb):
  count = 0
  bulbs = bulb[:]
  for i in range(1, n):
    if bulbs[i - 1] == target[i - 1]: # 만약 타겟과 같은 값을 가지면
      continue # 패스
    count += 1 # 타겟과 다른 값을 가지면 count +1
    for j in range(i - 1, i + 2): # 현재 전구의 앞 ~ 뒤까지 반복문 실행
      if j < n: # n(전구개수)을 넘어가지 않을 때까지만
        bulbs[j] = 1 - bulbs[j] # 스위치 누르기
  if bulbs == target:
    return count
  else:
    return 1e9

# 첫번째 전구를 누르지 않았을 때
answer = change(bulb)

# 첫번째 전구를 눌렀을 때
bulb[0] = 1 - bulb[0]
bulb[1] = 1 - bulb[1]
answer = min(answer, change(bulb) + 1)

if answer == 1e9:
  print(-1)
else:
  print(answer)

 

+ 추가적으로 알게된 점

( 1 ) 함수의 파라미터를 추가할수록 시간이 늘어난다. 입력받을 파라미터의 개수를 늘리기 보단, 함수 내에서 직접 정의해주는 것이 시간적으로 큰 향상을 보였다.

( 2 ) 함수를 사용할 때 파라마터로 리스트를 받아 그대로 리스트를 변형해주면 안된다. 함수 안에서만 변형이 되는 것이 아니라 실제 리스트에 변형이 일어나기 때문에 함수 내에서는 깊은 복사를 통해 새로운 변수에 리스트를 할당하여 사용해주어야 한다.