[백준 11057번] 오르막 수 - 자바스크립트(nodejs)

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

11057번: 오르막 수

const { off } = require('process');
const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input;

rl.on('line', function (line) {
  input = +line;
  rl.close();
}).on('close', function () {
  const dp = Array.from(Array(input + 1), () => new Array());

  dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
  dp[2] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

  for (let i = 3; i <= input; i++) {
    for (let j = 0; j < dp[i - 1].length; j++) {
      const value = [...dp[i - 1]];

      dp[i][j] = value.slice(0, j + 1).reduce((acc, cur) => acc + cur) % 10007;
    }
  }

  console.log(dp[input].reduce((acc, cur) => acc + cur) % 10007);
});

전형적인 DP문제이다. 쉬운 DP문제에서 가장 많이 사용하는 용법인 것 같다.

 

N
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55
4	1	4	10	20	35	56	84	120	165	220

N은 그냥 윗 부분의 index만큼 더한 값을 넣어주면 된다.

ex) N이 4인 경우에서 3번째 인덱스인 20은 N이 i-1인 3에서 1+3+6+10 한 결과와 같음! 

코딩테스트에서 DP문제를 봤을 때 누적되는 느낌이 든다면 위처럼 동작하는 지 확인해보자