💡 문제
N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.
N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.
출력
첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.
💭 접근
이 문제는 0을 1로, 1을 0으로 바꾼다는 점에서 1080번 행렬 문제와 유사하다. 그러나 1080번 행렬 문제의 경우 반드시 3x3 범위만큼 상태를 바꾸지만, 이 문제의 경우 첫번째 스위치를 누르면 i와 i+1번째 전구를, 나머지 스위치는 i-1, i, i+1번째 전구를 바꾼다는 점에서 다르다.
또한 모든 스위치를 누르는 경우의 수를 구하여 브루트 포스 관점으로 접근하면 주어지는 입력의 크기가 100,000이므로 시간초과가 발생하게 된다.
따라서 이 문제는 다른 방식으로 접근해야 하는데, 모든 전구를 순차적으로 탐색하며 상태가 다르면 스위치를 눌러 상태를 바꾼다. 이때 i-1번째 전구를 기준으로 상태가 다르면 i번째 스위치를 눌러준다.
그러나 위와 같은 방식으로 구현하면 문제가 하나 발생하는데, i-1번째 전구를 기준으로 i번째 스위치를 누른다면 "첫번째 스위치는 눌러야하는가?" 이것이 모호해진다.
따라서 처음에 첫번째 스위치를 누르지 않은 상태에서 탐색을 하고, 이렇게 해도 해결되지 않는다면 첫번째 스위치를 누른 다음 다시 탐색을 진행하면 문제가 해결된다.
📒 코드
def toggle(i):
if tmp[i] == 0: tmp[i] = 1
else: tmp[i] = 0
n = int(input())
a = list(map(int, input()))
b = list(map(int, input()))
ans = 0
tmp = a[:]
for i in range(1, n):
if i != n - 1:
if tmp[i - 1] != b[i - 1]:
ans += 1
for j in range(i - 1, i + 2):
toggle(j)
else:
if tmp[i - 1] != b[i - 1]:
ans += 1
for j in range(i - 1, i + 1):
toggle(j)
if tmp == b:
print(ans)
else:
ans = 1
tmp = a[:]
for i in range(2):
toggle(i)
for i in range(1, n):
if i != n - 1:
if tmp[i - 1] != b[i - 1]:
ans += 1
for j in range(i - 1, i + 2):
toggle(j)
else:
if tmp[i - 1] != b[i - 1]:
ans += 1
for j in range(i - 1, i + 1):
toggle(j)
if tmp == b:
print(ans)
else:
print(-1)💭 후기
아직 그리디 알고리즘이 익숙하지 않다. 많이 풀어보고 계속 복습하자.
🔗 문제 출처
https://www.acmicpc.net/problem/2138
