2138

날짜 : 2023. 4. 19

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
now = sys.stdin.readline().rstrip()
check = sys.stdin.readline().rstrip()  # 목표값
a = list()
b = list()


def flip(idx, arr):
    for i in range(idx - 1, idx + 2):
        if 0 <= i < len(arr):
            if arr[i] == "0":
                arr[i] = "1"
            else:
                arr[i] = "0"
    return


res1, res2 = 0, 0

for i in now:
    a.append(i)  # 첫 번째 수 flip
    b.append(i)  # 두 번째 수부터 flip

for i in range(n):
    if i == 0:
        res1 += 1
        flip(i, a)
        #print(i, a, b, res1, res2)
        continue
    if a[i-1] != check[i-1]:  # 이전 인덱스와 비교했을 때 다른 경우 뒤집기
        res1 += 1
        flip(i, a)
    if b[i-1] != check[i-1]:
        res2 += 1
        flip(i, b)
    #print(i, a, b, res1, res2)

t1, t2 = "", ""
for i in range(n):
    t1 += a[i]
    t2 += b[i]
if t1 == check and t2 == check:  # 둘 다 성공
    print(min(res1, res2))
else:
    if t1 == check and t2 != check:
        print(res1)
    elif t1 != check and t2 == check:
        print(res2)
    else:
        print(-1)

 

 

풀이

- 우선 전구의 스위치를 눌러서 flip하는 케이스는 기준점 이전의 전구값과 목표값이 서로 다른 경우로 정의한다.

- 이를 바탕으로 두 가지 케이스를 위해 두 개의 리스트를 만든다.

- 하나(a)는 첫 번째 전구를 기준으로 스위치를 누른 경우와 두 번째(b)는 누르지 않았을 때의 케이스이다.

- 이를 바탕으로 for문을 활용해서 각각의 인덱스 바로 앞의 전구상태를 비교해서 스위치를 누르고 이를 변경한다.

- 그다음, 해당 리스트의 최종 결과값과 원하는 결과값을 비교해서 a와 b 모두 성공했을 때, 혹은 하나만 성공했을 때, 아니면 전부 성공하지 못했을 때의 케이스를 나누어서 값을 출력한다.

 

 

알게된 점

- 전구의 스위치를 누를 때 그 기준점을 가운데로만 생각하는 바람에 삼천포로 빠졌다.

- 그래서 구글링을 활용해 두 가지 케이스로 나누어 풀이하는 방식을 참고했고, 문제를 풀었다.

- 마지막에는 채점을 돌리다가 62%쯤에서 오답을 확인했고 그 결과 a와 b 모두 가능한 반례가 존재한다는 것을 확인, 전부 가능, 하나만 가능, 전부 불가능 이 세 케이스로 나누어서 값을 출력하는 것으로 조건문을 작성했더니 정답이 나왔다.

- 그리디가 뭔가 발상은 되게 간단한데 그 과정이 너무 어려운 것 같다...

 

 

참고 사이트

-