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

백준 2138번

✔️ 문제 풀이

◾ 그리디 알고리즘

• 문제의 로직은 크게 어렵지 않지만, 1번 스위치를 누를지 말지로 케이스를 나누는 것을 떠올리지 못하면 헤맬 수 있다.
• 두 케이스로 나눠줘야하는 이유
  ⇒ 뒤집기 문제에서는 정답과 다른 원소를 발견하면 해당 원소를 기준으로 뒤집기를 하는데, 1번 스위치를 누르는 경우는 존재하지 않는 원소가 기준이 됨으로 뒤집어야 하는지 뒤집지 않아야 하는지를 판단할 수 없다.
  ⇒ 두 가지 케이스로 나눠서 풀이
• 0 ~ n-2의 원소에 대해서 해당 인덱스의 원소가 목표값과 일치하는지 확인하고, 일치하지 않으면 뒤집어준다.
  (문제에서는 스위치를 기준으로 ±1 범위를 뒤집는다고 설명하지만, 실제 구현은 인덱스를 기준으로 +2까지 뒤집음으로 n-1가 아닌 n-2까지 검사한다.)
• 각각의 케이스에서 도출된 값을 비교하여 정답을 출력한다.

최종 제출 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
array1 = list(map(int, input().rstrip()))
array2 = array1[:]
array3 = list(map(int, input().rstrip()))

converted = [False]*n

def convert(array, index):
  if array[index] == 1:
    return 0
  else:
    return 1

# 첫번째 스위치를 누르는 경우
case1 = 1

array1[0] = convert(array1, 0)
array1[1] = convert(array1, 1)

for i in range(n-1):
  if array1[i] != array3[i]:
    for j in range(3):
      if i+j < n:
        array1[i+j] = convert(array1, i+j)
    case1 += 1

if array1[n-1] != array3[n-1]:
  case1 = -1

# 첫번째 스위치를 안 누르는 경우
case2 = 0

for i in range(n-1):
  if array2[i] != array3[i]:
    for j in range(3):
      if i+j < n:
        array2[i+j] = convert(array2, i+j)
    case2 += 1

if array2[n-1] != array3[n-1]:
  case2 = -1

# 출력값
# 두 케이스 모두 정답으로의 전환이 가능한 경우는 최소값을 출력해줘야 하지만
# 어느 한 쪽이라도 -1이면 최대값을 출력해줘야 한다
print(min(case1, case2) if case1 != -1 and case2 != -1 else max(case1, case2))

✔️ 실행 결과