백준 2138 전구와 스위치 Python

🐸 문제 정보

2138번: 전구와 스위치

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

failed

 

📝 풀이

dp로 풀다가 도저히 모르겠어서 찾아보니 그리디였다........

그리디로 푸는 방법은 생각보다 간단했다.

직전 전구만 비교하되, 첫 번째 전구의 경우에는 직전 전구가 없기 때문에

첫번째 전구를 건들지 않고 시작한 경우와 / 첫번째 전구를 건들고 시작한 경우

두개로 나눠서 비교하면 되는 문제였다.

 

🧑‍💻 나의 답

import sys
input = sys.stdin.readline

n = int(input().rstrip())
bef = list(map(int, list(input().rstrip())))
obj = list(map(int, list(input().rstrip())))
res = []

def change(temp):
    cur = bef[:]
    for i in range(1, n):
        if cur[i - 1] != obj[i - 1]:
            temp += 1
            for j in range(i - 1, i + 2):
                if j < n: cur[j] = 1 - cur[j]
    if cur == obj:
        return temp
    return sys.maxsize

res.append(change(0))

bef[0] = 1 - bef[0]
bef[1] = 1 - bef[1]
res.append(change(1))
ans = min(res)

if ans == sys.maxsize:
    print(-1)
else:
    print(ans)