백준 SILVER 5(다리 놓기)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-01-28

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • 각 다리를 놓는 경우를 확인하는데 최대 30 x 30
    • n = 1, m = n부터 시작해 최대 N, M까지 각 dp를 업데이트
      • n === m인 경우 놓을 수 있는 다리 수는 1개
      • n === 1인 경우 놓을 수 있는 다리 수는 m개
      • 그 외의 경우 이전 dp 값들의 누적 합

  • 회고 :

    • x

  • 코드

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

solution(input);

function solution(props) {
  props = props.split('\n').slice(1);

  props.forEach((prop) => {
    const [N, M] = prop.split(' ').map((e) => +e);
    const dp = Array.from({ length: 30 }, () => Array(30).fill(0));

    for (let n = 1; n <= N; n++) {
      for (let m = n; m <= M; m++) {
        if (n === m) {
          dp[n][m] = 1;
        } else if (n === 1) {
          dp[n][m] = m;
        } else {
          for (let i = 1; i < m; i++) {
            dp[n][m] += dp[n - 1][i];
          }
        }
      }
    }
    console.log(dp[N][M]);
  });
}

  • 출처: 백준