[Baekjoon 2138 / Python / 골드4] 전구와 스위치

문제

 

그리디 문제이다. 문제는 간단한데 해결 방법이 도저히 떠오르질 않았다. 한번에 3개의 전구가 바뀌니까 엄청나게 많은 경우의 수가 있을 것이라 생각했고, 아무리 생각해도 답을 도출할 방법이 떠오르질 않아서 다른 코드를 참고했다. 근데 참고해도 이해가 잘 안된다. 이 코드가 어째서 정답을 도출하는지.

 

이론적으론 이해했지만 와닿지가 않는다.

# 그리디

import sys

input = sys.stdin.readline

N = int(input())

origin = list(map(int, input().strip()))

target = list(map(int, input().strip()))

# 1번 인덱스 전구부터 하나씩 누를지 말지 결정하는 함수

def solve(A, B):

    press = 0

    for i in range(1, N):

        if A[i-1] == B[i-1]: # 이전 전구가 같다면 누르지 않는다

            continue

        else: # 이전 전구가 다르다면 누른다

            press += 1

            A[i-1] = 1 - A[i-1]

            A[i] = 1 - A[i]

            if i+1 < N: A[i+1] = 1 - A[i+1] # i+1번이 존재한다면 바꿔준다

   

    return press if A == B else int(1e9)

# 첫 번째 스위치를 누르지 않은 경우

string = origin[:]

result = solve(string, target)

# 첫 번재 스위치를 누른 경우

origin[0] = 1 - origin[0]

origin[1] = 1 - origin[1]

result = min(result, solve(origin, target) + 1) # 두 개를 비교해서 result 결정

# 정답 출력

print(result) if result != int(1e9) else print(-1)

 

 

가장 중요한 포인트는 이것이었다.

전구는 켜져 있거나 꺼져 있거나 두 가지 상태밖에 없다. 즉, 2번 누르면 원래대로 돌아간다. 유효한 경우의 수는 각 스위치를 누르거나/누르지 않거나 2가지밖에 없으며, 즉 우리는 하나의 스위치에 대하여 그것을 누를지 말지만 정하면 된다. 돌아가서 다시 누른다거나 이럴 필요가 없다. 단 한번 순회하며 누를지 말지만 정해주면 된다.

 

그러면 여기서 문제가 생긴다. 누를지 말지를 어떤 기준으로 정할 것인가?

이렇게 생각하면 된다. 앞에서부터 목표 전구와 같도록 1개씩 맞춰 가기.

 

맞춰 간다는 건 무엇을 의미하는가? 한번 설정해 두면 이후로 변하지 않고 고정된 상태가 되는 것을 의미한다.

그렇다면 언제 고정된 상태가 되는가? 앞에서부터 순회한다고 가정했을 때 i-1번 전구의 상태는 i번 스위치에 의해서 최종적으로 결정된다. 즉 다음 스위치에 의해 결정된 후 그 뒤로는 고정되며, 바뀌지 않는다. 즉 우리는 i-1번 전구가 목표 전구와 동일한 상태인지를 확인하고, 동일하다면 누르지 않고 동일하지 않다면 눌러주면 되는 것이다. 이렇게 앞에서부터 하나씩 목표 전구와 상태를 맞춰갈 수 있다.

 

단, 여기서 또 하나의 예외가 생긴다. 첫번째(0번 인덱스) 전구는 비교할 앞 전구가 없다는 것이다. 따라서 두 가지 경우의 수를 모두 고려한다. 첫 번째 전구를 누르거나, 누르지 않거나. 두 경우를 고려해서 더 적은 횟수로 목표를 달성한 값을 출력해 주면 되는 것이다. 이렇게 풀면 리스트를 단 한번 순회하여 정답을 도출할 수 있으며, 따라서 최악 시간복잡도는 O(N)이 되겠다. O(2N)이긴 한데 상수는 제외하고.

 

이 문제는 왜 그리디인가? 그리디는 항상 부분 최적해를 우선시하는 알고리즘이다. 이 문제는 앞에서부터 전구를 한개씩 확인하며 목표 전구와 같은 상태로 만든다. 즉 뒤쪽에서 어떻게 될 지는 생각하지 않고 당장 하나의 전구를 맞춰가는 것을 우선시한다. 그리고 그것이 정답을 도출한다. 따라서 이 문제는 그리디 알고리즘으로 볼 수 있다.

 

하지만 이론적으로는 이해해도 뭔가 와닿지가 않는다. 이 방식으로 풀면 분명 모든 경우의 수를 고려하여 최소값을 찾아낼 수 있지만.. 뭔가 잘 모르겠다. 그리디, DP 문제들의 특징인 것 같다. 그냥 자주 풀면서 이런 풀이가 당연하게 느껴지도록 반복하는 수 밖에 없을지도 모르겠다.

 

 

결과