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

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

아이디어가 도저히 생각 안나서 다른풀이 참고해서 풀었다;;

N이 크기때문에 모든 경우의수는 당연히 따질수없다..따라서 첫번째 스위치부터 시작해서 그리디하게 경우의수를 줄여나가야 한다.

이로부터 얻은 핵심 아이디어는 i위치에서 0부터 i-1까지는 정답과 같아야 다음으로 넘어갈수 있다는 것이다.

왜냐하면 i+1에서는 i는 바꿀 수 있지만 i-1를 바꿀 수 없기 때문이다. 따라서 i 위치에서 i-1가 정답과 같은 경우에만 넘어간다. 다시말해 i-1가 정답과 같다면 그대로 넘어가고, 다르다면 i를 바꾼다음에 넘어간다.

이런 맥락에서부터 첫번째 전구가 켜져있어도 두번째 전구에 의해 꺼질수 있고, 반대의 경우도 가능하기 때문에 처음 시작하는 첫번째 스위치에 대해서는 1,0인 경우 모두 따져서 진행해야한다.

처음에 0부터 위치 x까지 같은지 확인해주는 isSame(x) 함수를 작성해서 풀었는데 시간초과가 났다 ㅠ
그런데 다시 생각하면 굳이 문자열 첫번째부터 확인할필요 없다...
어차피 i에서는 0부터 i-2까지는 이미 확인하고 넘어온것이기 때문에, i-1에 대해서만 같은지/다른지 확인하고 같으면 i를 바꾸지 않고, 다르면 i를 바꾸고 넘어가면 된다.

#include <iostream> 
#include <vector> 
using namespace std;

int ans=-1;
int N;
string str1, str2;


char change(char c){
    if(c=='0') return '1';
    else return '0';
}

/*bool isSame(string &s, int k){

    for(int i=0; i<k; i++){
        if(s[i]!=str2[i]) return false;
    }

    return true;
}*/

void solve(string &s, int cnt, int x){

    if(x==N) {
        if(s[x-1]==str2[x-1]) {
            if(ans==-1) ans = cnt;
            else ans = min(ans, cnt);
        }
        return ;
    }

    // x에서 바꾸는경우 or 안바꾸는경우 따짐
    // x-1까지는 무조건 같아야함 x+1에서는 영향 못미치므로

    if(s[x-1]==str2[x-1]) solve(s, cnt, x+1);
    else {
        s[x-1] = change(s[x-1]);
        s[x] = change(s[x]);
        if(s[x+1]!=N) s[x+1]=change(s[x+1]);
        solve(s, cnt+1, x+1);
    }

    return ;

}


int main(){

    cin>>N;
    cin>>str1>>str2;

    string tmp = str1;

    solve(str1, 0, 1);

    if(ans==-1){
        str1=tmp;
        str1[0] = change(str1[0]);
        str1[1] = change(str1[1]);
        solve(str1, 1, 1);
    }


    cout<<ans;


}