문제
N종류(최대 5)의 구슬이 각각 주어진 개수만큼 있을 때, 연속 2개가 같은 종류가 되지 않도록 배열하는 경우의 수를 구하라.
입력
첫째 줄에 N, 이후 N줄에 각 종류의 구슬 개수가 주어진다.
출력
유효한 배열의 경우의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 2 2 | 2 |
풀이
7차원 메모이제이션 DP로 이전 2개 색상과 각 색상 남은 수를 상태로 관리한다.
- 상태: (5종류의 남은 개수, 직전 색상, 직전 직전 색상)
- 재귀적으로 남은 구슬 중 이전 2개와 다른 색을 선택하여 배치한다
- 모든 구슬을 배치하면 1을 반환한다
- Map으로 상태를 키로 만들어 메모이제이션한다
핵심 아이디어: N이 최대 5이고 각 구슬 수가 작아 상태 공간이 관리 가능하며, 이전 2개만 추적하면 연속 조건을 검증할 수 있다.
코드
const solution = (input) => {
const N = +input[0];
const cnt = [];
for (let i = 1; i <= N; i++) cnt.push(+input[i]);
while (cnt.length < 5) cnt.push(0);
const memo = new Map();
const key = (a, b, c, d, e, p1, p2) =>
`${a},${b},${c},${d},${e},${p1},${p2}`;
const recur = (a, b, c, d, e, prev1, prev2) => {
if (a + b + c + d + e === 0) return 1;
const k = key(a, b, c, d, e, prev1, prev2);
if (memo.has(k)) return memo.get(k);
let result = 0;
const arr = [a, b, c, d, e];
for (let i = 0; i < 5; i++) {
if (arr[i] === 0 || i === prev1 || i === prev2) continue;
arr[i]--;
result += recur(arr[0], arr[1], arr[2], arr[3], arr[4], i, prev1);
arr[i]++;
}
memo.set(k, result);
return result;
};
return recur(cnt[0], cnt[1], cnt[2], cnt[3], cnt[4], -1, -1);
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(상태 수 × 5) (메모이제이션으로 중복 제거)
- 공간: O(상태 수)