[BOJ] 백준 2138 전구와 스위치 c++ (그리디)

문제 출처 : https://www.acmicpc.net/problem/2138

2138번: 전구와 스위치

---

풀이

이 문제는 아이디어가 잘 떠오르지 않는 문제였다.. 다른 여러 풀이를 참고했다.

• 현재 전구를 반복문을 돌린다.
• i 기준일때 i-1번째까지 정답과 일치하면 넘어간다.
  • 이유는 i+1번째로 기준이 넘어가면 i-1은 더이상 영향을 받지 않기 때문이다.
• i-1번째가 일치하지 않는다면 스위치를 누른다.(뒤집기)
• 이 경우를 그냥 시작하는 경우 / 가장 처음에 뒤집고 시작하는 경우로 나누어 실행한다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int ans = -1;
int N;
string from, to;

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

void solution(string &str, int cnt, int x){
    if(x == N){
        if(str[x-1] == to[x-1]){
            if(ans == -1) ans = cnt;
            else ans = min(ans, cnt);
        }
        return;
    }

    if(str[x-1] == to[x-1])
        solution(str, cnt, x+1);
    else{ // 뒤집기
        str[x-1] = change(str[x-1]);
        str[x] = change(str[x]);
        if(x+1 < N)
            str[x+1] = change(str[x+1]);
        solution(str, cnt+1, x+1);
    }
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> from >> to; 
    
    string tmp = from;
    solution(from, 0, 1);

    if(ans == -1){
        from = tmp;
        from[0] = change(from[0]);
        from[1] = change(from[1]);
        solution(from, 1, 1);
    }
    cout << ans << '\n';
    return 0;
}