BOJ 2138 전구와 스위치

1번부터 n번까지 전구가 일렬로 놓여있고, 각각의 전구는 켜져있는 상태 또는 꺼져있는 상태이다. i번 스위치를 누르면, i-1, i, i+1번 전구의 상태가 반대로 바뀐다. (1번 스위치를 누르면 1, 2번 전구의 상태가 바뀌고, n번 스위치를 누르면 n-1, n번 전구의 상태가 바뀐다) 그래서 n개의 전구들의 현재 상태와, 만들고자 하는 상태가 주어졌을 때 그 상태를 만들기 위해 스위치를 최소 몇번 눌러야 하는지 구하는 문제이다.(불가능한 경우에는 -1 출력한다)

스위치 하나당 바꿀 수 있는 범위가 자기 위치를 포함 양 옆으로 한 칸씩 이다보니 각 전구의 상태를 바꿀 수 있는 스위치는 최대 3개까지 있는데, 같은 스위치를 2번 누를일은 없기 때문에 1번 스위치부터 보면, 일단, 1번 전구의 상태를 바꿀 수 있는 스위치는 2개가 존재(1, 2번 스위치)하는데, 1번 스위치부터 시작해서 전구의 상태를 결정해버리면(1번 스위치를 어떻게 쓸 것인지 결정하면) 이제 1번 전구의 상태를 바꿀 수 있는 스위치는 2번 스위치 하나밖에 없다. 그럼 2번 스위치를 쓸 것인지 안 쓸 것인지 결정하면 이제 2번 전구의 상태를 결정할 스위치는 3번 스위치 하나밖에 없게되고... 같은 스위치를 2번 누를 일은 없기 때문에(최소 횟수 구하는 것이라서... 같은 스위치를 2번 누르는 것은 아예 누르지 않는 것과 같다) 이렇게 1번 스위치 부터 시작해서 상태를 결정해 나가면 된다.

결국 1번 스위치를 누를 것이냐 안 누를 것이냐 이 2가지 경우에 대해서 O(n)만에 횟수를 구할 수 있을 것 같다.

이 문제는 직접 코드를 짜보고 풀어봐야 이해가 잘 된다... 그래서 직접 해봤는데 맞았다. 1번 스위치부터 시작해서 상태를 결정하면 1번 전구부터 차례로 상태를 결정할 수 있는 방법이 한 가지만 남게 되어서 바꿔야하는 상태와 비교해서 스위치를 누를지 안 누를지 결정할 수 있게 된다. 그렇게 결정하다보면 결국 (n번째까지 있다면 n-1번 전구까지 결정하면 맨 마지막 n번째 전구의 상태가 저절로 결정되어)맨 마지막 전구의 상태는 바꿀 수 없게 되고 바꿔야 하는 상태의 맨 마지막 전구의 상태를 비교해서 같으면 가능한 것이고 다르면 불가능 한 것이라는 것을 알 수 있다.


출처 : 백준님 문제풀이 강의, 백준님 풀이 자료