백준 2138 전구와 스위치(c++)

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

2138번: 전구와 스위치

이 문제는 0번 스위치를 누를지 말지 결정하고 풀어야 하는 문제입니다. 왜냐하면 모든 스위치를 한 번씩 눌러보는 브루트 포스로는 복잡도 문제로 해결할 수 없습니다. 0번 스위치를 누른다면, 1번 스위치만 신경 쓰면 되고, 1번 스위치가 눌러지면 2번 스위치만 고려하면 되기 때문입니다. 그래서 시간 복잡도 O(N)으로 풀 수 있게 됩니다.

 

<코드>

#include <cstdio>
#include <vector>

using namespace std;

void change(vector<int> &a, int index)
{
    for (int i = index - 1; i <= index + 1; i++)
    {
        if (0 <= i && i < a.size())
        {
            a[i] = 1 - a[i];
        }
    }
}

pair<bool, int> go(vector<int> a, vector<int> &goal)
{
    int n = a.size();
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] != goal[i])
        {
            change(a, i + 1);
            ans += 1;
        }
    }
    if (a == goal)
    {
        return make_pair(true, ans);
    }
    else
    {
        return make_pair(false, ans);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    vector<int> goal(n);

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

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

    auto p1 = go(a, goal);
    // 0번 전구 선택 x
    change(a, 0);
    auto p2 = go(a, goal);
    // 0번 전구 선택
    if (p2.first)
    {
        p2.second += 1;
    }
    if (p1.first && p2.first)
    {
        printf("%d\n", min(p1.second, p2.second));
    }
    else if (p1.first)
    {
        printf("%d\n", p1.second);
    }
    else if (p2.first)
    {
        printf("%d\n", p2.second);
    }
    else
    {
        printf("-1");
    }
    return 0;
}