BOJ 2138 전구와 스위치

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

2138번: 전구와 스위치

 

원래는 14639번을 풀려고 했는데... 아무리 생각해도 못 풀고 힌트를 들어도 못 푸니까 cologne 님이 던져준 문제입니다.

 

연속된 전구가 주어지고 $i$번째 전구는 $i-1$, $i$, 그리고 $i+1$번째 전구를 toggle 할 수 있습니다. 원래의 전구 상태와 바꾸고자 하는 전구 상태가 주어질 때, 최소 toggle 횟수를 찾아야 합니다.

 

이는 그리디한 방법으로 찾을 수 있습니다. 첫 번째 전구에 영향을 줄 수 있는 전구는 첫 번째 전구와 두 번째 전구 뿐입니다. 먼저 첫 번째 전구의 스위치를 누르지 않기로 결정했다고 합시다. 그러면 첫 번째 전구에 영향을 줄 수 있는 전구는 두 번째 전구만 남게 됩니다. 따라서 이 때 원래의 첫 번째 전구 상태와 바꾸고자 하는 첫 번째 전구 상태가 다를 경우 두 번째 전구는 무조건 스위치를 눌러야 합니다. 이렇게 두 번째 전구의 스위치를 누를지가 결정되면 두 번째 전구에 영향을 줄 수 있는 전구는 세 번째 전구밖에 남지 않고, 이 작업을 계속 수행하면 그리디하게 원래 상태에서 바꾸고자 하는 상태로 가는 최소이자 유일한 횟수를 구할 수 있습니다.

 

이를 첫 번째 전구의 스위치를 누르는 경우와 누르지 않는 경우, 두 가지로 나눠서 수행하면 그 중 최솟값이 정답이 됩니다. 이 때, 위의 알고리즘을 전부 수행한 뒤의 전구 상태가 원래 전구 상태와 다를 경우 바꿀 수 없는 경우가 됩니다.

 

뭔가 14639번을 풀 수 있을거 같기도 하고... 내일 풀어봐야겠어요.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

const int MOD = 1e6 + 3;
const int INF = 0x3f3f3f3f;

using namespace std;

int T, n;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    string s1, s2;
    cin >> s1 >> s2;

    vector<int> ans(n);
    vector<int> now(n);
    for (int i = 0; i < n; i++) ans[i] = s2[i] - '0';
    for (int i = 0; i < n; i++) now[i] = s1[i] - '0';

    int a = INF;
    
    int cnt = 0;
    for (int i = 1; i < n; i++) {
      if (now[i - 1] != ans[i - 1]) {
        now[i - 1] = !now[i - 1];
        now[i] = !now[i];
        if (i + 1 < n) now[i + 1] = !now[i + 1];
        cnt++;
      }
    }
    if (now == ans) a = min(a, cnt);

    for (int i = 0; i < n; i++) now[i] = s1[i] - '0';
    now[0] = !now[0];
    now[1] = !now[1];

    cnt = 1;
    for (int i = 1; i < n; i++) {
      if (now[i - 1] != ans[i - 1]) {
        now[i - 1] = !now[i - 1];
        now[i] = !now[i];
        if (i + 1 < n) now[i + 1] = !now[i + 1];
        cnt++;
      }
    }
    if (now == ans) a = min(a, cnt);

    if (a == INF) cout << -1 << endl;
    else cout << a << endl;
  }

  return 0;
}