👓 문제 설명
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을 출력한다.
🚨 접근 방법
주어진 예제를 직접 풀어보았다.
3
000
010
1,2,3번 스위치를 모두 눌렀을 때 010의 결과를 얻는다.
그러면 1,2,3번 스위치를 누르는 순서에 따라 결과가 달라질까 확인해보았다.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
모두 결과는 010으로 동일했다.
결국 토글 방식의 ON OFF는 순서와 관련 없이 모두 독립적으로 전구에 영향이 미치므로 동일한 스위치를 누른다 했을 때 순서는 상관이 없었다.
조합으로 해결한다면 N이 최대 10만이라서
2의 10만 제곱의 시간이 소모된다.
-> 시간초과!
순서에 상관 없다면 앞에서부터 해결하면 되지 않을까 생각했다.
양 끝의 스위치만 특별한 경우로
자기 자신과 바로 옆 1개의 전구만 ON/OFF를 수행한다.
그래서 크게 2가지 경우로 나누었다.
1. 첫번째 스위치가 눌렸을 때
2. 첫번째 스위치가 눌리지 않았을 때
이후, 첫번째 전구는 첫번째 스위치 이후 두번째 스위치의 영향만 받는다.
이는 다시 말하면 앞에서부터 스위치를 킬때,
(i>0) i-1번째 전구는 i번째 스위치를 통해 조절해야만 한다.
(0번째 전구를 ON/OFF 두가지로 확정 지어 구분했을 때 한정)
🚈 풀이
// 0번을 누를때 안누를때
// 이후, 1번 부터 자신의 앞 스위치를 눌러야 하는지 말아야 하는지 판단
#include<iostream>
#include<climits>
#define MAX INT_MAX
using namespace std;
int n;
int ans = MAX;
string s1, s2;
void switchOn(bool first_on) {
string temp = s1;
int cnt = 0;
if (first_on)cnt = 1;
for (int i = 1; i < n; i++) {
if (temp[i - 1] != s2[i - 1]) {
temp[i - 1] = s2[i - 1];
if (temp[i] == '0')temp[i] = '1';
else temp[i] = '0';
if (i < n - 1) {
if (temp[i + 1] == '0')temp[i+1] = '1';
else temp[i+1] = '0';
}
cnt++;
}
}
if (temp == s2)ans = min(ans, cnt);
}
void func() {
cin >> s1 >> s2;
char first = s1[0];
char second = s1[1];
// 0번을 누를 때
for (int i = 0; i < 2; i++) {
if (s1[i] == '0')s1[i] = '1';
else s1[i] = '0';
}
switchOn(true);
// 0번을 안누를 때
s1[0] = first;
s1[1] = second;
switchOn(false);
if (ans == MAX)cout << -1;
else cout << ans;
}
int main() {
cin >> n;
func();
return 0;
}