2138번 전구와 스위치

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

 

 

0번 스위치를 누를 때와 누르지 않을 때 2가지 경우를 나누어 구현한다.

 

 

idea)

i번 째 스위치를 누를지 말지 고민하는 상황일 때,

현재 i-1번 째 스위치의 현재 상태와

우리가 만들고자 하는 전구의 i-1번 째 스위치의 상태가 다르면

눌러야 한다.

 

 

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 200000

int n, now[MAX], now2[MAX], goal[MAX], ans1, ans2;

bool isSame() {
    for (int i = 0; i < n; i++) {
        if (now[i] != goal[i]) {
            return false;
        }
    }
    return true;
}

int main()
{
    cin.tie(0);

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%1d", &now[i]);
        now2[i] = now[i];
    }

    for (int i = 0; i < n; i++) {
        scanf("%1d", &goal[i]);
    }

    // 0번 스위치를 안 눌렀을 때
    for (int i = 1; i < n; i++) {
        // 1번 스위치부터 시작
        
        // 이전 i-1번 째 스위치(now, goal)의 상태가 다를 경우,
        // 현재 i번 째 스위치를 누른다.
        if (now[i - 1] != goal[i - 1]) {
            ++ans1;
            // 누르면, i-1, i, i+1의 전구 상태가 변한다.
            if (i - 1 >= 0) now[i - 1] = 1 - now[i - 1];
            now[i] = 1 - now[i];
            if (i + 1 < n) now[i + 1] = 1 - now[i + 1];
        }
    }

    // 같지 않다면
    if (!isSame()) {
        ans1 = -1; // -1로 초기화
    }

    // 초기 상태로 초기화
    for (int i = 0; i < n; i++) {
        now[i] = now2[i];
    }

    // 0번 스위치를 눌렀을 때
    ++ans2;
    now[0] = 1 - now[0];
    now[1] = 1 - now[1];

    for (int i = 1; i < n; i++) {
        if (now[i - 1] != goal[i - 1]) {
            ++ans2;
            if (i - 1 >= 0) now[i - 1] = 1 - now[i - 1];
            now[i] = 1 - now[i];
            if (i + 1 < n) now[i + 1] = 1 - now[i + 1];
        }
    }

    // 같지 않다면
    if (!isSame()) {
        ans2 = -1; // -1로 초기화
    }

    /*
    같이 않을 때, -1이 아니라 0으로 초기화하면 안 된다. 답이 0이 나올 수 있음.
    2
    01
    01
    correct : 0
    wrong : 2
    */

    if (ans1 == -1 && ans2 == -1) printf("-1\n");
    if (ans1 == -1 && ans2 != -1) printf("%d\n", ans2);
    if (ans1 != -1 && ans2 == -1) printf("%d\n", ans1);
    if (ans1 != -1 && ans2 != -1) printf("%d\n", min(ans1, ans2));

    return 0;
}