Post

Posted Updated
By Changjin Kang
views 6 min read

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

문제 요약

  • 0이면 꺼진 전구, 1이면 켜진 전구를 의미하는 전구들의 상태 A, B가 주어진다.

  • i번째 전구 스위치를 누르면, i-1, i, i+1 3개의 인접한 전구의 상태가 바뀐다.

  • A 상태를 B 상태로 바꾸기 위해 스위치를 최소 몇번 눌러야 하는지 구해야 한다.

  • 바꾸는 것이 불가능할 수 있으며 이 경우 -1을 출력한다.

예제

1
2
3

N = 3
A = 000
B = 010
  1. A의 0번 스위치를 누르면 110 으로 상태가 변한다
  2. A의 1번 스위치를 누르면 001 으로 상태가 변한다.
  3. A의 2번 스위치를 누르면 010 으로 상태가 변한다.

총 3번 스위치를 눌렀고, A 상태에서 B 상태로 변경되었으므로 답은 3이다. (3보다 적게 누를 수 없음)

풀이

1. 전구를 누르는 순서는 상관이 없다.

가령 위의 예제에서 1->0->2 순으로 누르거나, 2->1->0으로 눌러도 똑같은 상태가 된다.

즉 누르는 순서를 신경쓸 필요 없이 0번 스위치부터 N-1번 스위치까지 순차적으로 돌면서 해당 스위치를 눌러도 될지 말지만 결정하면 된다.

2. 순차적으로 탐색한다면 i번째 스위치가 i-1번째 전구의 상태를 결정할 마지막 스위치이다.

다시 예제를 보자

1
2

A = 000
B = 010

0번째 스위치를 누른 경우

  • 0번째 스위치를 누른 경우 A는 110이다.
  • 1번째 스위치에서는 반드시 스위치를 눌러야한다. 왜냐하면 A와 B가 같기 위해서는 A[0] = B[0] = 0이어야 하는데, 현재 110 상태에서 스위치를 누르지 않고 지나가면 A[0]이 영원히 1이 되기 때문이다.
  • 1번째 스위치를 눌렀다면 A는 001이다.
  • 2번째 스위치 역시 반드시 스위치를 눌러야한다. A[1] = B[1] = 1이 되어야 하는데 현재 A[1] = 0이기 때문이다.

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

  • 0번째 스위치를 누른 경우 A는 000이다.
  • 1번째 스위치에서는 반드시 스위치를 누르지 않아야 한다. 1번 스위치를 누르면 A[0] 값이 영원히 1이 되기 때문이다. 여전히 A의 상태는 000이다.
  • 반대로 2번째 스위치는 반드시 눌러야한다. A[1] 값이 1이 되어야 하기 때문이다. 그러나 2번째 스위치를 누르면 A의 상태는 011이 되어 A != B이다.

결론

즉 0번째 스위치만 누를지 말지만이 경우의 수이며, 나머지는 모두 A[i-1], B[i-1] 값에 따라 고정된다. 이를 코드로 구현하면 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import sys

input = sys.stdin.readline

# 스위치를 눌렀을 때 상태 변경을 해주는 함수
def reverse(bulbs, count):
    for i in range(1, N-1):
        if bulbs[i-1] != target[i-1]:
            count += 1
            for j in range(i-1, i+2):
                bulbs[j] = not bulbs[j]
    # 마지막 전구만 따로 처리
    if bulbs[N-1] != target[N-1]:
        count += 1
        bulbs[N-2] = not bulbs[N-2]
        bulbs[N-1] = not bulbs[N-1]
    if bulbs == target:
        return count
    else:
        return -1


N = int(input())

# not을 이용해 간편하게 처리하고 싶어서 0:False, 1:True의 bool 값으로 바꾸었다.
off = list(map(bool, map(int, input().rstrip())))

# 0번째 스위치를 누른 상태를 저장하는 리스트
on = off.copy()
on[0] = not on[0]
on[1] = not on[1]

target = list(map(bool, map(int, input().rstrip())))

# 처음부터 상태가 같은 경우 스위치를 눌러줄 필요가 없으니 0 출력
if off == target:
    print(0)
else:
    # 0번째 전구를 안눌렀을 때
    count = reverse(off, 0)
    if count != -1:
        print(count)
    else:
        # 0번째 전구를 눌렀을 때
        count = reverse(on, 1)
        print(count if count else -1)

코멘트

그리디 유형의 문제를 많이 안풀어봐서 최근 많이 풀어보고 있는데, 확실히 난이도(티어)에 비해 많이 어렵게 느껴지는 것 같다.

단순히 그리디라고 하면 이득이면 하고, 아니면 말고 식의 문제인줄 알았는데 경우의 수를 고정해서 푸는 방법을 생각하지 못했다.

당분간 그리디를 많이 풀면서 익숙해지도록 하자.

This post is licensed under CC BY 4.0 by the author.