백준 - 2138 전구와 스위치 (파이썬)

문제 링크 : https://www.acmicpc.net/problem/2138
난이도 : 골드 5

문제풀이

---

문제 정리

• 현재 전구의 상태와 목표로 하는 전구의 상태가 주어진다. 목표하는 전구의 상태로 만들기 위해 스위치를 몇 번 눌러야할지 구해야한다.
• N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다.
• 하지만1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

분석

• 필요로 하는 알고리즘이 떠오르지 않을때는 브루트 포스를 생각할 수 있다.

• 브루트 포스를 생각해보면 다음과 같은 상황이라고 생각 해볼 수 있다.

  • 스위치는 최대 1번 - 10만번 켤 수 있다
  • 스위치를 n번 (1<n<10만) 켜는 경우는 $Combination(10만,n)$ 으로 구할 수 있다.
  • 하지만 n을 1에서 10만까지 따져봐야되기 때문에 엄청나게 큰 경우의 수가 필요하다는 결론에 다다른다.

• 때문에 현재 인덱스에서 켤지 말지에 대한 판단(현재 상황에서 최적의 해 또는 부분 최적해)이 필요하고, 어떻게 부분 최적해를 결정할지 고려해야한다. 이는 그리디를 의미한다.

• 부분 최적해는 이전 전구 전체를 비교하지않고, 바로 직전 인덱스의 전구를 비교하여 스위치를 켤지 말지 정할 수 있따.

   A_copy = A[:]
    press = 0
    for i in range(1, n):
    	  # 전체를 비교하지 않고 직전만 비교, 같다면 스위치를 누르지 않음
  	  if A_copy[i-1] == B[i-1]:
    		continue
        press += 1
        # 다르면 스위치를 누름
        for j in range(i-1, i+2):
           if j<n:
              A_copy[j] = 1 - A_copy[j]

• 그리고 시작 스위치를 고려해주어야 하는데, 시작 스위치를 누를때 안누를 때에 따라 경우를 구해야한다.

  • 시작 스위치를 누를 때, 안 누를 때 분리해야하는 이유

    • 1100110 현재 전구 상태이고 0100110를 목표 전구 상태라 하자
      - 첫번째 스위치를 누를 때
      0000110
      - 첫번째 스위치를 누르지 않고 두번째 스위치를 누를 때
      0010110

      • 첫번째를 누르는 경우와 첫번째를 누르지 않고 두번째를 누르는 경우
      • 두 경우에 따라 뒤쪽에 눌러야하는 경우의 수가 다 바뀜
      • 때문에 두 경우에서 최솟값을 구해 비교해줘야한다.

• 그리디 문제는 어려워질수록 부분 최적해를 구하는 아이디어는 물론, 아이디어를 적용하는 경우의 수까지 고려하게 만든다.

시간복잡도

• $O(n)$ 으로 충분히 해결할 수 있다.

전체코드

---

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


def change(A, B):
    A_copy = A[:]
    press = 0
    for i in range(1, n):
        
        if A_copy[i-1] == B[i-1]:
            continue
        
        press += 1
        for j in range(i-1, i+2):
            if j<n:
                A_copy[j] = 1 - A_copy[j]
    if A_copy == B:
        return press 
    else:
        return 1e9

res = change(bulb, target)
# 첫번째 전구의 스위치를 누르는 경우
bulb[0] = 1 - bulb[0]
bulb[1] = 1 - bulb[1]
#비교
res = min(res, change(bulb, target) + 1)# min(첫번째 전구x, 첫번째 전구 o)
if res != 1e9:
    print(res)
else:
    print(-1)

정리 및 느낀점

---

• 그리디 문제는 어려워질수록 부분 최적해를 구하는 아이디어는 물론, 아이디어를 적용하는 경우의 수까지 고려하게 만든다.