전구와 스위치

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

2138번: 전구와 스위치

이전의 전구의 상태를 기준으로 다음 스위치를 누를 지 말지를 결정

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void change(vector<int>& a, int index)
{
    for (int i = index - 1; i <= index + 1; i++)
    {
        if (i >= 0 && i < a.size())
            a[i] = 1 - a[i];
    }
}
 
// pair<가능, 스위치를 누르는 횟수>
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;
    cin >> 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);
 
    //첫번째를 키고 카운트
    // 이 떄는 a(n)이 바뀌게 된다 &를 썼으므로
    change(a, 0);
    auto p2 = go(a, goal);
 
    // 첫번쨰를 켰으니까!
    if (p2.first)
        p2.second += 1;
 
    if (p1.first && p2.first)
        cout << min(p1.second, p2.second) << '\n';
    else if (p1.first)
        cout << p1.second << '\n';
    else if (p2.first)
        cout << p2.second << '\n';
    else
        cout << -1 << '\n';
 
    return 0;
}