[골드 5] 2138번: 전구와 스위치

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

2138번: 전구와 스위치

---

문제

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을 출력한다.

---

사고의 흐름

• BFS 아닌가? 이 문제가 Greedy라고?
• 그런데 애초에 이 문제에서 BFS를 돌리기도 애매하다. 방문 처리를 해야 하는 Case가 너무 많으니까.
• 우선 숫자 자체가 중요하지는 않다는 사실은 알겠다. 주어지는 전구의 상태 숫자와 만들고자 하는 전구의 상태 숫자가 같냐, 다르냐가 중요하다. bool 타입 List를 하나 만들어서 서로 같으면 True, 다르면 False를 저장해놓고 시작해야겠다.

 

• 가만 생각해보니 문제가 행렬 문제와 비슷하다. 그렇다면 이 문제도 한쪽에서부터 탐색하면서 서로 다른 전구를 발견했을 때 스위치를 눌러주면 되는 건가? 그래서 다 눌렀을 때 서로 다른 전구가 있으면 -1을 띄우면 되나?
• 행렬 문제도 그렇고 이 문제도 그렇고 정당성 증명 방법을 잘 모르겠다. 일단 제출해보고 맞으면 정당성 증명 방법을 찾아봐야겠다.
• 틀렸네. 모르겠다. 답을 보자.

남이 작성한 소스코드

lee308812 님:
https://staticvoidlife.tistory.com/143

피드백

• 행렬 문제보다는 2×n 타일링 문제와 더 비슷한 문제였다. 복잡해 보이는 조건을 Case를 나누어 풀어가는 방식이 유사하다.
• 생각 외로 정당성 증명을 하지 않고 Greedy 문제를 푸는 사람이 많았다. 하지만 아직 나는 학생이니 기초부터 탄탄하게 다져가면서 공부하도록 하자.
• Case를 나누는 게 익숙하지 않아서 그렇지, Case를 나누는 방식에 익숙해지면 Greedy도 수월하게 풀 수 있을 것 같다.