백준 2138 : 전구와 스위치 - javascript(그리디)

문제 출처 

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

 

정답 풀이 

브루트포스와 그리디를 함께 이용한다. 

첫번째 스위치를 클릭하는 경우와 클릭하지 않는 경우를 각각 확인한다. 

 

풀이 접근 

1. 첫번째 스위치 클릭 기준 :

첫번째 전구의 상태를 바꾸면 나머지 전구의 상태도 다르게 변화하기 때문에 이를 기준으로 삼는다. 

 

2. 그리디 :

첫번째 스위치 선택 이후에는 두번째부터 차례대로 조작을 결정하여 목표 상태와 맞추어 나간다. 

 

정답 코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const n = Number(input[0]);
const initial = input[1].split('').map(Number);
const target = input[2].split('').map(Number);

function toggle(arr, index) {
    for (let i = index - 1; i <= index + 1; i++) {
        if (i >= 0 && i < n) {
            arr[i] = arr[i] === 0 ? 1 : 0; // 0이면 1로, 1이면 0으로 토글
        }
    }
}

function countSwitches(initial, target, pressFirst) {
    const bulbs = [...initial]; // 전구 배열 복사
    let count = 0;

    if (pressFirst) { // 첫 번째 전구를 누르는 경우
        toggle(bulbs, 0);
        count++;
    }

    for (let i = 1; i < n; i++) {
        if (bulbs[i - 1] !== target[i - 1]) {
            toggle(bulbs, i);
            count++;
        }
    }

    // 목표 상태와 일치하는지 확인
    for (let i = 0; i < n; i++) {
        if (bulbs[i] !== target[i]) {
            return Infinity; // 목표 상태로 만들 수 없는 경우
        }
    }

    return count;
}

const result1 = countSwitches(initial, target, true); // 첫 번째 스위치를 누르는 경우
const result2 = countSwitches(initial, target, false); // 첫 번째 스위치를 누르지 않는 경우

const answer = Math.min(result1, result2);
console.log(answer === Infinity ? -1 : answer);