[Python] 2538. 전구와 스위치 / 그리디

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

2138번: 전구와 스위치

---

2. 핵심 아이디어

https://staticvoidlife.tistory.com/143

[그리디 알고리즘] 전구와 스위치

---

3. 코드

#2138. 전구와 스위치(골5)

import sys
import copy
#input = lambda:sys.stdin.readline().strip('\n')

#스위치 바꾸는 함수
def switch_on(light, i, n):
  for idx in (i-1, i, i+1):
    if idx>=0 and idx<n:
      light[idx]= abs(light[idx]-1)

n= int(input())
light= [int(i) for i in list(input())]
light1= copy.deepcopy(light)
target= [int(i) for i in list(input())]
cnt=0

result1=0
result2=1

# i-1이 확정되었다면 i번째만이 i-1을 바꿀 수 있다
#스위치를 누르지 않았을 때 => i-1에 영향을 주는 것을 i번째밖에 없음
for i in range(1, n):
    if(light[i-1]!= target[i-1]):
      result1+=1
      switch_on(light, i, n)

#스위치 눌렀을 때
switch_on(light1, 0, n)

for i in range(1,n):
    if(light1[i-1]!= target[i-1]):
      result2+=1
      switch_on(light1, i, n)

flag1=True
flag2=True

light =list(map(str, light))
light1= list(map(str, light1))
target = list(map(str, target))

# 변환이 가능한지 확인
if ''.join(light) != ''.join(target):
  flag1=False
  result1= sys.maxsize

if ''.join(light1) !=''.join(target):
  flag2=False
  result2=sys.maxsize

# 둘다 불가능한지 체크
if flag1==False and flag2==False:
  print(-1)
else:
  print(min(result1, result2))

---

비슷한 문제

9082번: 지뢰찾기

4.배운점

그리디 아이디어는 재능이 아닌 노력으로 극복이 가능한 문제일까...?!

역대급으로 아이디어를 떠올리기 힘든 문제였다. 내 힘으로 푼 것 같진 않지만 아이디어를 체화할 수 있도록 며칠이 지난 후 다시 풀어봐야 겠다..