백준 GOLD 5(합분해) - #2225

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-02-08

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • N이 1인 경우 k개
    • K가 1인 경우 1개 (N 하나)
    • K가 2인 경우 N+1개
    • K가 3인 경우
      • N이 2인 경우 6개 (0+0+2, 2+0+0, 0+2+0, 1+1+0, 1+0+1, 0+1+1)
      • N이 3인 경우 10개 (0+0+3, 0+3+0, 3+0+0, 2+1+0, 2+0+1, 1+2+0, 1+0+2, 0+1+2, 0+2+1, 1+1+1)
    • 이를 통해 점화식 dp[i][j] = dp[i][j-1][i-1][j] (i >=2, j>=2) 도출

  • 회고 :

    • N, K로 dp 초기화하면 런타임 에러

  • 코드

    const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim();

solution(input);

function solution(props) {
  const [N, K] = props.split(' ').map((e) => +e);
  const dp = Array.from({ length: 201 }, () => Array(201).fill(0));

  for (let i = 1; i <= 200; i++) {
    dp[1][i] = 1;
    dp[2][i] = i + 1;
  }

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

  console.log(dp[K][N]);
}

  • 출처: 백준