2138 - 전구와 스위치

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

2138번: 전구와 스위치

생각해보기

• 처음 버튼을 누른 경우와 누르지 않은 경우 2가지가 존재한다.
• 메커니즘상 현재 버튼이 아닌 다음 버튼을 누르므로 2가지 경우를 모두 따져봐야 한다.
• 현재 버튼이 아닌 경우 다음 버튼을 누르는 방식으로 진행하여 맨 마지막 버튼이 정답과 일치하는지 확인한다.

코드

#include<iostream>
#include<algorithm>

using namespace std;

int N;
string now, result;

void input(){
    cin>>N>>now>>result;
}

//맨 앞부터 다른 경우 다음 위치의 버튼을 눌러가며 진행, 맨 마지막 원소로 최종 확인
int calc(string str){
    int cnt = 0;
    for(int i=0;i<str.length()-1;++i){
        if(str[i] != result[i]){
            for(int j=0;j<3;++j){
                if(i+j >= str.length())
                    continue;
                str[i+j] = str[i+j] == '0' ? '1' : '0';
            }
            ++cnt;
        }
    }

    //마지막 원소가 동일하면 true
    if(str.back() == result.back())
        return cnt;
    return 987'654'321;
}

void solution(){
    //처음 버튼을 누른 경우
    string copy = now;
    copy[0] = copy[0] == '0' ? '1' : '0';
    copy[1] = copy[1] == '0' ? '1' : '0';

    //처음 버튼을 누른 경우와 안누른 경우중 더 작은 값
    int ans = min(calc(copy)+1, calc(now));

    if(ans == 987'654'321)
        cout<<-1<<'\n';
    else
        cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}