[BOJ] 전구와 스위치

[BOJ] 전구와 스위치

Problem URL : 전구와 스위치

#include <iostream>
#include <string>
#include <algorithm>
#define INF 987654321

using namespace std;

int N, answer;
bool current[100000], goal[100000];

void push(int idx) {
    if (idx > 0) {
        current[idx - 1] = !current[idx - 1];
    }
    current[idx] = !current[idx];

    if (idx < N - 1) {
        current[idx + 1] = !current[idx + 1];
    }
}

void dfs(int idx, int cnt){
    if (cnt >= answer) {
        return;
    }
    if (idx == N){
        bool flag = true;
        for (int i = 0; i < N; i++) {
            if (current[i] != goal[i]) {
                flag = false;
                break;
            }
        }
        if (flag) answer = min(answer, cnt);
        return;
    }
    
    //[1]
    if (current[idx - 1] == goal[idx - 1]) dfs(idx + 1, cnt);
    push(idx);
    if (current[idx - 1] == goal[idx - 1]) dfs(idx + 1, cnt + 1);
    push(idx);
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string init, end;    
    cin >> N >> init >> end;
    for (int i = 0; i < N; i++) {
        if (init[i] == '1') {
            current[i] = true;
        }
        if (end[i] == '1') {
            goal[i] = true;
        }
    }
    
    answer = INF;
    dfs(1, 0);
    push(0);
    dfs(1, 1);

    if (answer == INF) {
        cout << -1 << "\n";
    } else {
        cout << answer << "\n";
    }
    return 0;
}

Comments

[1] 한칸씩 오른쪽으로 이동하면서, 왼쪽의 전구들을 목표값이랑 같게 만들어주는게 핵심