백준 32174 컵 쌓기

문제

N종류의 컵이 있는데 해당 컵의 입구를 포개서 나올 수 있는 경우의 수를 구하는 문제이다. 컵의 수에는 제한이 없으므로 브루트포스로 풀면 될 것 같지만

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, h] = inputs[0].split(" ").map(Number);
const cups = inputs[1].split(" ").map(Number);
 
let acc = 0;
function search(height) {
  if (height === h) {
    acc++;
  }
  if (height > h) return;
  for (let i = 0; i < n; i++) {
    search(height + cups[i]);
  }
}
backTrack(0);
console.log(acc);
 

이렇게 풀면 경우의 수가 너무 높게 올라가기 때문에 시간제한에 맞추지 못한다. 그러나 다시 생각해보면 이 문제는 작은 문제로 분할할 수 있다. dp 배열에 각 인덱스를 i라고 한다면, i번째 요소에는 i가 가질 수 있는 경우의 수를 기록하고이전 값, 그러니까 하나씩 내려가면서 h-1 , h-3 …등의 각 컵의 높이를 뺀 값들을 누적시켜주면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, h] = inputs[0].split(" ").map(Number);
const cups = inputs[1].split(" ").map(Number);
const MOD = 1000000007;
 
const dp = new Array(h + 1).fill(0);
dp[0] = 1;
 
for (let i = 1; i <= h; i++) {
  for (const cup of cups) {
    if (i >= cup) {
      dp[i] = (dp[i] + dp[i - cup]) % MOD;
    }
  }
}
console.log(dp);
console.log(dp[h]);