[JS] 백준 2225번 : 합분해 - DP, 파스칼의 삼각형

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

2225번: 합분해

 

 

📋풀이방법

1. K와 N의 상관관계를 표로 나타내보았다.

2. 이를 통해 DP[K]N]의 값은  DP[K][N-1] 과 DP[K-1][N] 의 합으로 구할 수 있습니다

- 왜냐하면 DP[K][N-1] (왼쪽 파란색) 자체가 이미 DP[K-1][0] 부터 DP[K-1][N-1] 까지의 합 (이전 표에서 위쪽 파란색) 을 반영한 것이기 때문에, 그 값을 바로 더해줘도 되는 것입니다.

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

const [n, k] = input.shift().split(" ").map(Number);

let dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(1));

for (let i = 2; i < k + 1; i++) {
  for (let j = 1; j < n + 1; j++) {
    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
  }
}

console.log(dp[k][n]);

 

 

 

💢어려웠던 점

1. DFS를 이용해서 풀었지만 시간초과가 났다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

const [N, K] = input.shift().split(" ").map(Number);

let visited = Array.from({ length: N + 1 }, () => 0);
let count = 0;

function DFS(L, sum) {
  if (sum > N) return;
  if (L > K) return;
  if (L == K && sum == N) {
    count++;
  } else {
    for (let i = 0; i <= N; i++) {
      DFS(L + 1, sum + i);
    }
  }
}

DFS(0, 0);
console.log(count);

- 답은  잘 나오지만 시간초과가 난다.