[백준] 10844. 쉬운 계단 수 (자바스크립트/javascript/js/node.js/동적프로그래밍/동적계획법/다이나믹프로그래밍)

2021. 7. 9. 12:53Front-end/알고리즘

728x90
반응형

 

 

문제를 풀기 위한 아이디어

다이나믹 프로그래밍 문제는 언제나 점화식을 세우는 것이 중요하다.

이번 문제는 dp에서 2차원 배열을 이용해서 저장하는 것을 배울 수 있었던 문제였다.

 

우선 0으로 시작하는 수는 없다고 했기 때문에,

n=1인 경우 1,2,3,4,5,6,7,8,9 = 9가지 경우가 나온다.

n=2인 경우를 생각해보자. (10,11) (21,23)  .... (98)로 다 합치면 17가지 경우가 나온다. 

즉 앞의 수가 0이면 뒤에 올 수 있는 수는 1밖에 존재하지 않는다.

만약 앞의 수가 1부터 8이라면 각각 두개씩 존재할 수 있다.

만약 앞의 수가 9라면 뒤에 올 수 있는 수는 8밖에 존재하지 않는다. 이를 염두해두어야 한다.

 

dp[n][i]를 n자리수 이면서 i로 끝나는 경우라고 한다면,

우선 n=1인 경우는 dp[1] = [0,1,1,1,1,1,1,1,1,1]; 라고 저장해놓는다.

n=2인 경우는 dp[2] = [1,1,2,2,2,2,2,2,2,1];가 된다.

- dp[2][0] = 자리수가 2이면서 0으로 끝나는 수는 10밖에 존재하지 않으므로 1,

- dp[2][1] = 자리수가 2이면서 1로 끝나는 수는 21 밖에 존재하지 않으므로 1,

- dp[2][2] = 자리수가 2이면서 2로 끝나는 수는 12, 32로 2개가 존재하므로 2,

  ...

- dp[2][9] = 자리수가 2이면서 9로 끝나는 수는 89 밖에 존재하지 않으므로 1)

 

n=3인 경우부터는 어떨까?

- dp[3][0] = 자리수가 3이면서 0으로 끝나는 수이다. 0으로 끝나기 때문에 바로 직전의 수는 1밖에 올 수 없다. 즉 dp[2][1]의 개수(자리수가 2이면서 1로 끝나는 수의 개수)가 된다. 

- dp[3][1]  = 자리수가 3이면서 1로 끝나는 수 이다. 1로 끝나기 때문에 바로 직전의 수는 0과 2가 올 수 있다. 즉 dp[2][0] + dp[2][2]가 된다. (자리수가 2이면서 0으로 끝나는 수 + 자리수가 2이면서 2로 끝나는 수)

  ...

- dp[3][9] = 자리수가 3이면서 9로 끝나는 수 이다. 9로 끝나기 때문에 바로 직전의 수는 8밖에 올 수 없다. 즉 dp[2][8] (자리수가 2이면서 8로 끝나는 수) 이다.

 

즉 점화식을 세워본다면 n=3부터는

1) i = 0인 경우

dp[n][i] = dp[n-1][i+1]

2) i = 1부터 i = 8까지 인 경우

dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]

3) i = 9인 경우

dp[n][i] = dp[n-1][i-1]

위와 같은 식이 성립한다.

 

문제에서 10억으로 나눈 값을 출력하라고 했으므로 저장할 때에도 10억으로 나눈 나머지를 저장하고,

출력할 때에도 10억으로 나눈 나머지를 출력한다.

 

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
const number = Number(fs.readFileSync("예제.txt").toString());

// dp[n][i] = n자리 수이면서 i로 끝나는 수
const dp = Array.from(new Array(number + 1), () => new Array(10));

dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1];

for (let n = 3; n <= number; n++) {
  for (let i = 0; i < 10; i++) {
    if (i === 0) {
      dp[n][i] = dp[n - 1][i + 1] % 1000000000;
    } else if (i >= 1 && i <= 8) {
      dp[n][i] = (dp[n - 1][i - 1] + dp[n - 1][i + 1]) % 1000000000;
    } else {
      dp[n][i] = dp[n - 1][i - 1] % 1000000000;
    }
  }
}
let sum = 0;
for (let j = 0; j < 10; j++) {
  sum += dp[number][j];
}

console.log(sum % 1000000000);
728x90
반응형