백준 13021 공 색칠하기

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

문제

기계를 사용했을 때 나올 수 있는 색 조합의 경우의 수를 모두 구하는 문제이다. 기계는 L번째 공부터 R번째 공까지 한 가지 색으로 칠하게 되어있다. L부터 R까지는 흑 백 두 가지의 경우의 수가 나온다는 의미이다. 하지만 여기에 기계를 사용했을 때 얘네들이 기존에 칠해져 있던 공을 덧칠할 수도 있다. 이럴 경우에는 새롭게 기계가 칠한 색으로 덧칠해주고 여기서 경우의 수를 찾아야 한다. 일반적인 알고리즘 기법이라기보다는 애드 혹으로 얘한테만 적용되는 알고리즘을 짜야 한다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [n, m] = inputs[0].split(" ").map(Number);
const balls = new Array(n + 1).fill(-1);
const ballPaints = inputs.slice(1).map((b) => b.split(" ").map(Number));
 
ballPaints.forEach(([l, r], i) => {
  for (let j = l; j <= r; j++) {
    balls[j] = i;
  }
});
 
let cnt = 0;
 
let group = {};
for (let i = 1; i <= n; i++) {
  if (balls[i] !== balls[i - 1] && balls[i] >= 0) {
    if (group[balls[i]]) {
      continue;
    } else {
      cnt++;
      group[balls[i]] = 1;
    }
  }
}
console.log(Math.pow(2, cnt));
 

나는 그냥 배열을 같은 크기로 만든담에 기계가 색칠하는 케이스에 따라 인덱스로 칠해주었다. 이렇게 되면 덧칠하는 경우도 기존의 값이 덮어씌워지게 되어 정상적으로 계산을 할 수 있다.

처음에는 이렇게 한 담에 if (balls[i] !== balls[i - 1] && balls[i] >= 0)의 조건만 걸었는데 바로 엣지케이스에 걸려버렸다. 이유는 15까지 공을 칠한 경우와 23까지 공을 칠한 경우가 있다고 할 때, 내 알고리즘 상으로는 1, 2~3, 4~5세 가지의 경우로 보기 때문이다. 하지만 1과 4~5는 같은 시간에 같은 색으로 채워진 경우이기 때문에 함께 고려하여 계산해야 한다. 그래서 그룹을 따로 두어 기존에 없던 그룹만 카운트를 추가하고, 마지막에 2의 cnt 제곱을 계산했다.