[BOJ] 2138 전구와 스위치 (node.js)

링크

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

 

 

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

풀이 과정

접근법 1. 완전 탐색

우선적으로 전체 스위치를 순회하면서 끄고 / 켜는 경우를 생각해볼 수 있다.

 

하지만 시간 복잡도를 계산해보면

 

전체 스위치의 최대 갯수가 100,000개일 때 전체 스위치를 켜고 끄는 경우의 수는 2(켜기/끄기)^N이고, 

결과에 대해 목표하는 전구 상태와 비교해야 하므로 N회의 연산이 필요하다.

 

즉, O(N * 2^N)의 시간 복잡도가 발생하고, 이는 최대 N인 100,000을 대입했을 때 시간 초과가 발생하게 된다.

 

접근법 2. 그리디

그렇다면 효율적으로 푸는 방법을 찾아야 한다.

 

해당 문제같은 경우에 연산 횟수를 줄이기 위해 DP나 그리디를 고려해볼 수 있다.

 

하지만 이 문제와 같은 경우에 i번 스위치를 켜면 i-1, i, i+1 전구에 영향을 미치기 때문에 

DP로는 해결할 수 없다. (DP는 이전 위치까지의 상태를 보고 현재 상태의 최적 해를 결정하기 때문)

 

구체적으로 말하면 3번 스위치를 켜면 2, 3, 4번의 전구 상태가 변경되기 때문에, 만약 2번에서 최적해를 확정지어도 미래에 값이 변경될 수 있기 때문에 '각 위치에서의 최적해를 확정짓는' DP로는 해결할 수 없는 것이다.

 

그렇다면 그리디로 생각해보자.

나는 그리디적인 풀이를 떠올리다가 도무지 떠오르지 않아 다른 사람의 풀이를 참고했다.

 

로직을 작성하면 아래와 같다.

 

1. 우선 첫 번째 스위치를 누르는 경우와 누르지 않는 경우를 분리한다.

* 첫 번째 스위치를 누르는 경우와 누르지 않는 경우를 분리해야 하는 이유

예를 들어 [1 1 0]이 현재 전구 상태이고 [0 0 0]이 목표 전구 상태라고 할 때,

1) 첫 번째 스위치를 눌렀을 때 => [0 0 0]
2) 첫 번째 스위치를 누르지 않고, 두 번째 스위치를 눌렀을 때 => [0 0 1]

1)번에서 스위치를 한 번 누름으로써 최적해를 찾았다.
만약 2가지 경우를 분리하지 않고 첫 번째 스위치를 누르는 경우를 처리하지 않았다면, 최적해를 찾을 수 없다.

 

2. 각각의 경우에 두 번째 전구부터 마지막 전구까지 목표하는 상태와 비교하면서 스위치를 조작한다.

* 이때 i번 스위치를 켤지 말지 결정할 때는 i번 전구 상태를 비교하는게 아니라, i-1번 전구의 상태를 비교하여 같지 않을 때만 i번 스위치를 켜준다.

아래와 같을 때,
스위치 번호 : [1 2 3]
현재 전구 :    [1 1 1]
목표 전구 :    [1 0 0]

3번 스위치를 켤지 결정할 때는 2번째 전구의 현재 전구와 목표 전구의 상태를 비교해야 한다.
만약 2번 위치의 전구의 상태가 다르다면 3번 스위치를 켜야하기 때문이다.

 

이렇게 스위치를 조작하는 행위를 왼쪽에서 오른쪽으로 진행할 수 있는 이유는

 

i번 스위치는 i-1, i, i+1 전구에 영향을 미치고, 그렇기 때문에 i번 스위치는 i-1번 전구의 최종 상태를 결정짓는 마지막 기회가 되기 때문이다. i+1번 이상의 스위치가 i-1번째 전구의 상태를 결정할 수는 없다.

 

따라서 i-1번 전구의 최종 상태를 결정하기 위해서는 i번 스위치를 켤지 말지 반드시 선택해야한다.

 

 

코드

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

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

const change = (x) => {
  return x === 1 ? 0 : 1;
};

const calc = (status) => {
  let cnt = 0;

  for (let i = 1; i < N; i++) {
    if (target[i - 1] === status[i - 1]) continue;

    cnt++;

    for (let j = i - 1; j <= i + 1; j++) {
      status[j] = change(status[j]);
    }
  }

  let flag = true;

  for (let i = 0; i < N; i++) {
    if (status[i] !== target[i]) {
      flag = false;
      break;
    }
  }

  return flag ? cnt : Infinity;
};

let cnt1 = calc([...cur]);

cur[0] = change(cur[0]);
cur[1] = change(cur[1]);

let cnt2 = calc([...cur]);
if (cnt2 !== Infinity) cnt2 += 1;

let answer = cnt1 === Infinity && cnt2 === Infinity ? -1 : Math.min(cnt1, cnt2);

console.log(answer);

 

 

후기

첫 번째 스위치를 누르는 경우와 누르지 않는 경우를 구하고, 해당 결과의 최솟값을 구해야 한다는 생각을 못했다.

이런 사고에 익숙해지려면 역시 문제를 많이 풀어야 겠다.

 

참고

https://velog.io/@waoderboy/BOJ-%EB%B0%B1%EC%A4%80-2138-%EC%A0%84%EA%B5%AC%EC%99%80-%EC%8A%A4%EC%9C%84%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[BOJ] 백준 - 2138 전구와 스위치 (파이썬)