백준 2138 전구와 스위치

문제

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

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

제한 사항

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

입출력 예

풀이

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


const sol = (input) => {
  const n = +input.shift();
  const cur = input.shift().split("").map(Number);
  const target = input.shift().split("").map(Number);

  const compare = (a, b) => {
    for (let i = 0; i < n; i++) {
      if (a[i] !== b[i]) return false;
    }
    return true;
  };

  
  const push = (idx, tmp) => {
    // idx가 0보다 크면 즉, 첫번째 전구가 아니라며 전 전구도 바꾼다.
    if (idx > 0) {
      tmp[idx - 1] = tmp[idx - 1] ? 0 : 1;
    }
    // 현재 전구를 바꾼다.
    tmp[idx] = tmp[idx] ? 0 : 1;
    // 마지막 전구가 아니라면, 다음 전구도 바꾼다.
    if (idx < n - 1) {
      tmp[idx + 1] = tmp[idx + 1] ? 0 : 1;
    }
  };

  const division = (firstOrNot) => {
    let tmp = [...cur];
    let min = Number.MAX_SAFE_INTEGER;
    let cnt = 0;
    // 들어오는 변수가 0이라면, 0번째 스위치를 누르고 시작하는 경우
    if (firstOrNot === 0) {
      tmp[0] = tmp[0] ? 0 : 1;
      tmp[1] = tmp[1] ? 0 : 1;
      cnt++;
    }
	// n번째 전구의 상태를 전환하기 위해서는 n+1번째 전구의 스위치를 눌러야한다.
    for (let i = 1; i < n; i++) {
      if (tmp[i - 1] != target[i - 1]) {
        push(i, tmp);
        cnt++;
      }
    }
    if (compare(tmp, target)) min = Math.min(min, cnt);
    return min;
  };
  let ans1 = division(0);
  let ans2 = division(1);
  const answer = Math.min(ans1, ans2);

  if (answer === Number.MAX_SAFE_INTEGER) {
    return -1;
  } else {
    return answer;
  }
};

console.log(sol(input));

이 문제를 알맞게 풀기 위해선 생각해 볼 점이 있다.

일단 스위치는 자신의 뒤, 앞에도 영향을 준다. 처음과 끝일 땐 각각 뒤와 앞에 영향은 줄 수 없다. 이걸 고려해서 만든 push 함수를 잘 읽어보자.

다음은 언제 스위치를 눌러야 하는가. 1, 2, 3번의 스위치가 있다고 전부다 꺼져있는 경우 1번 스위치를 켜고 싶다면 어떻게 해야할까? 1번은 눌러서 켜면 어차피 다음에 2번을 누르면 다시 꺼진다. 그러니 그냥 2번만 누른다면 1번이 켜지고 3번을 눌러도 1번엔 영향이 없다.
여기서 알 수 있는 것은 n번째 전구의 상태를 바꾸고 고정하려면 n+1번째 전구를 눌러야 한다는 것!! 이것은 중요한 포인트이다.

for (let i = 1; i < n; i++) {
      if (tmp[i - 1] != target[i - 1]) {
        push(i, tmp);
        cnt++;
      }
    }

이제 이 부분이 확실하게 이해가 갈 것이다. i일 때, i-1을 비교하고 다르다면 push!

거의다 왔다. 이제 변수가 생긴다. 첫번째 스위치를 누르고 시작할 것 인가. 누르지 않고 시작할 것인가. 그에 따른 각각의 count 값을 구해주고 정답을 구하면 된다.