[백준][DP] 4811 알약 NodeJs 구현

     

목차

1. 문제
2. 문제 구현 방향
3. 코드 구현

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

문제

 

 

문제 구현 방향

dp의 하향식으로 푸는 문제로 상태가 전체 알약인 경우와 반쪽 알약인 경우로 나누어

이차원 배열로 풀면 되는 문제이다.

 

 

코드 구현

javascript

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let dp = Array.from({ length: 31 }, () => Array(31).fill(0));

//반쪽 전체 두가지 상태

let idx = 0;
while (idx < input.length - 1) {
  let N = +input[idx];
  eating(0, N);
  idx++;
  console.log(dp[0][N]);
  
}

function eating(half, entire) {
  if (half === 0 && entire === 0) {
    //기저 조건
    return 1;
  }
  //중복 계산을 피하기 위한 조건
  if (dp[half][entire]) return dp[half][entire];
  if (entire > 0) {
    dp[half][entire] += eating(half + 1, entire - 1);
  }
  if (half > 0) {
    dp[half][entire] += eating(half - 1, entire);
  }
  return dp[half][entire];
}