[백준] 1034 램프

📖 문제

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

✏️ 나의 풀이

모든 경우의 수를 전부 찾을 경우 시간복잡도가 어마무시하게 커질 것 같다는 예감이 들었다. 그렇기에 불가능한 행을 먼저 제거하는 방식을 찾아봤다.

스위치를 1번 누르거나, 3번 누르는 경우 결과는 같다. 즉, 홀수번 스위치를 누르면 결과를 언제나 같다.

이런 성질을 이용해 불가능 행이 되기 위한 조건은 아래와 같다.

1. 꺼진 스위치가 k보다 작을 경우 ( k는 스위치를 누를 횟수 )
2. 꺼진 스위치가 k의 홀짝과 다를 경우

첫번째 경우는 쉽게 생각할 수 있지만 두번째의 조건은 찾기 어려웠다. 예를 들어보면 한 행의 전구 상태는 001이고 총 5번을 누를 예정이라 가정해보자.

우선 꺼진 2개의 전구를 키면 앞으로 스위치를 누를 기회는 3번으로 줄고 전구 상태는 111이 된다. 이상태에서 모든 전구를 2번씩 스위치를 눌러야 하지만 앞으로 3번밖에 누를 수 없으므로 이 행은 모든 전구를 킬 수 없다.

이러한 조건으로 코드를 작성하면 아래와 같다.

👩‍💻 코드

const solution = (input) => {
  input = input.split("\n");
  const [n, m] = input[0].split(" ").map(Number);
  const arr = input.slice(1, n + 1);
  const k = Number(input[1 + n]);
  const map = new Map();
  arr.forEach((v) => {
    if (map.has(v)) map.set(v, map.get(v) + 1);
    else {
      const count = v.split("").filter((s) => s === "0").length;
      if (count <= k && count % 2 === k % 2) map.set(v, 1);
    }
  });
  return map.size > 0 ? Math.max(...map.values()) : 0;
};

const path = "/dev/stdin";
const fs = require("fs");
const input = fs.readFileSync(path).toString().trim();

console.log(solution(input));