백준 2138. 전구와 스위치

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

2138번: 전구와 스위치

코드

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:  # j가 범위 안에 있을 때에만
                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)

if res != 1e9:
    print(res)
else:
    print(-1)

 

문제를 읽고 그리디 유형 문제들을 풀 때

3X3 행렬로 전체 행렬을 훑으면서 뒤집기 연산을 수행하는데

부분 행렬의 왼쪽 상단이 다르면 연산을 수행했던 것이 생각났다.

 

그 문제에서 풀었던 아이디어를

그대로 차용해서

현재 인덱스의 하나 전 전구 상태가 다르면

현재 인덱스의 스위치를 켜서 연산을 수행하면서

연산 수행 횟수를 카운팅 해주면 최소 연산 값이 나오겠다고 생각했다.

 

근데 문제는 N이 3인 경우와 2인 경우라고 생각했는데,

위에서 말한 아이디어의 일반화에 해당 두 경우가 들어가고

경우의 수로 나눠 생각해야 했던 부분은

맨 첫 번째 전구를 누를지 말 지에 대한 부분이었다.

 

위의 경우에 따라 뒤쪽에 눌러야 하는 경우의 수가 다 바뀌기 때문에

두 경우의 최솟값을 구해 비교해 정답을 구했다.

 

그리디 문제 유형은 어려워질수록

아이디어를 적용할 경우의 수를 고려해야 함을 깨달은 문제였다.

 

참고 자료

https://velog.io/@waoderboy/BOJ-%EB%B0%B1%EC%A4%80-2138-%EC%A0%84%EA%B5%AC%EC%99%80-%EC%8A%A4%EC%9C%84%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC