2138번 - 전구와 스위치

1️⃣ 탐욕 알고리즘

 

✏️ 풀이 과정

문제 풀이를 위해서는 특정한 가설을 세우고 진실 여부를 확인해야 하는데 바로 "각 스위치를 한 번씩만 눌러도 모든 경우의 수를 만들 수 있다."입니다. 이는 직관적으로 와닿을 수 있지 않은데 다음과 같이 생각하면 좋습니다. 스위치의 경우 ON과 OFF상태만이 존재하기 때문에 한 번 누르면 처음과 다른 상태, 두 번 누르면 처음과 동일한 상태가 됩니다.

 

여기서 주변 스위치에 의한 영향이 있지 않느냐 생각할 수 있지만 그 또한 주변 ON/OFF 여부에 따른 2가지 중 하나의 영향만을 받게 됩니다. 즉 자기 자신과 인접한 스위치들의 ON/OFF여부가 서로 상쇄된 결과가 최종 전구의 상태가 됩니다. 가령 인접한 3개를 다 눌렀을 경우 처음과 다른 상태, 2개가 눌린 경우 같은 상태, 1개인 경우 다른 상태, 0개인 경우 같은 상태가 됩니다. 따라서 각 스위치의 상태는 누르거나 누르지 않거나 밖에 없기때문에 모든 경우의 수는 각 스위치를 한 번 누르거나 한 번도 누르지 않음으로써만 발생합니다.(두 번 누르면 누르지 않은 것과 같습니다.)

 

아래 풀이에서는 위 전제 하에 두 가지 상태를 바탕으로 왼쪽 끝에서부터 스위치를 어떻게 작동시켜야하는지 계산하고 실제로 가능한 지의 여부를 판단합니다.

 

clicked는 이전 스위치를 눌렀는지의 여부이고 needed는 이전 스위치를 눌렀거나 누르지 않은 것이 이전 스위치를 기존 전구와 다음 상태의 해당 위치의 전구를 똑같게 만들기 위해 clicked와 같이 조작했다는 것을 의미합니다.(needed가 true이면 이번에는 눌러서는 안됩니다. 이번 스위치를 누르면 이전 상태가 바뀌기 때문에, 반대로 false면 무조건 눌러야 합니다.) clicked와 needed는 true, false로 총 4개의 조합을 만들고 각각의 상태는 단 하나의 다음 상태로 이어집니다.

 

이를 이용하면 마지막 스위치까지의 조작을 결정할 수 있는데 이 마지막 스위치의 needed가 true인 경우가 바로 가능한 경우입니다.(false일 경우 다음 스위치에서 조작해주는것을 염두에 두는 것인데 마지막이기 때문에 똑같이 만드는 것이 불가능합니다.)

 

한가지 더 생각해야하는 것은 맨 처음에 시작할 때 다음 스위치를 누를 것을 염두에 두고 바꿔야하는 것과 반대 상태인채로 다음으로 보내는 것과 바꿔야하는 대로 조작하는 것의 두 가지 선택지가 있다는 것입니다.

 

즉 needed를 true로 한 번, false로 한 번 초기값으로 주면서 dfs()함수를 실행하면 모든 경우의 수를 따질 수 있습니다. 이 때 둘 다 가능할 수도 있기 때문에 둘 중 더 작은 조작 횟수가 기록되도록 최솟값을 업데이트해줘야 합니다.

 

dfs()를 두 번 실행한 후에 최솟값을 출력하면 문제가 해결됩니다.

 

⏱ 시간 복잡도

dfs라고 적어두었지만 2*(N+1)번의 탐색이 이루어지기때문에 시간복잡도는 O(N)이 됩니다.

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const N = +input[0];
const cur = input[1].split("").map(Number);
const next = input[2].split("").map(Number);

let ans = Infinity;

const dfs = (n, clicked, needed, cnt) => {
    if (n == N) {
        if (needed) {
            ans = Math.min(ans, cnt);
        }
        return;
    }

    if (clicked) {
        if (needed) {
            if (cur[n] === next[n]) {
                dfs(n + 1, false, false, cnt);
            } else {
                dfs(n + 1, false, true, cnt);
            }
        } else {
            if (cur[n] === next[n]) {
                dfs(n + 1, true, true, cnt + 1);
            } else {
                dfs(n + 1, true, false, cnt + 1);
            }
        }
    } else {
        if (needed) {
            if (cur[n] === next[n]) {
                dfs(n + 1, false, true, cnt);
            } else {
                dfs(n + 1, false, false, cnt);
            }
        } else {
            if (cur[n] === next[n]) {
                dfs(n + 1, true, false, cnt + 1);
            } else {
                dfs(n + 1, true, true, cnt + 1);
            }
        }
    }
};

dfs(0, false, true, 0);
dfs(0, false, false, 0);

console.log(ans === Infinity ? -1 : ans);