[JS][백준]10844_쉬운 계단 수

문제 번호

10844번: 쉬운 계단 수

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 길이가 N인 계단수를 만드는 방법을 생각해본다. 길이가 3인 계단수 123 이 있다고 생각해보자. 이때 가장오른쪽에 있는 3뒤에 2나 4를 붙이면 1232 혹은 1234 라는 길이가 4인 계단수를 만들 수 있다.

 즉 길이가 N-1인 계단수의 뒤에 숫자를 추가해서 길이가 N인 계단수를 만들 수 있다는 말이다. 이를 위해서 2차원 배열을 사용하기로 하였다.

let dp = new Array(101).fill(null).map(_ => new Array(10).fill(0));

 대략 이렇게 생긴 2차원 배열을 만들 수 있다. 

문제에서 길이가 1인 숫자들은 모두 계단수라는것을 알 수 있다. dp[길이][시작하는숫자]로 사용한다.

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

 

 

 우리가 주의할점은 0과 9이다. 0으로 시작하는 숫자는 존재하지 않으며, 9의 경우 각 자리가 9보다 큰 경우가 없기 때문이다. 

 위에서 언급했듯이 우리는 길의 N의 계단수를 구하기위해서 길이가 N-1인 계단수에 숫자 1개씩을 추가할 것이다. 그러므로 j가 0과 9일때를 제외하면  dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라고 생각해 볼 수 있다. 

 dp[길이][시작하는숫자] 이므로 길이가 i인 계단수는 길이가 i-1 이면서 끝나는 숫자가 j-1이나 j+1 (계단수 조건)이면 j를 붙여서 만들 수 있는것이다. 

 dp[3][2] = dp[2][1] + dp[2][3]은 '길이가 3이고 2로 끝나는 계단수의 갯수는 길이가 2이고 1이나 3으로 끝나는 계단수의갯수를 합친것과 같다' 라는 뜻이다.

이제 2차원 배열을 위에서부터 가로로 채워나가면된다. 단, j가 0과 9일때만 주의를 하면된다. j가 0이면 마지막 i-1 단계에서 j가 1인 경우만 존재하고 j가 9면 i-1 단계에서 j가 8인 경우만 계단수를 만들 수 있다.

for (let i = 2; i <= N; i++) { // 자릿수.
    for (let j = 0; j < 10; j++) { // 시작하는 숫자.
      if (j === 0)
        dp[i][j] = (dp[i - 1][j + 1]) % divide;      
      if (j === 9)
        dp[i][j] = (dp[i - 1][j - 1]) % divide;
      if (1 <= j && j <= 8)
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % divide;
    }
  }

 

 이제 마지막으로 길이가 N인 모든 계단수들의 갯수를 더해서 출력하면된다. 길이가 N 이면서 0,1,2,.....9로 끝나는 모든 계단수를 구했다.

  for (let i = 0; i <= 9; i++) {
    answer += dp[N][i];
  }

 

전체코드

let N = +require('fs').readFileSync('input.txt').toString().trim().split('\n')
let dp = new Array(101).fill(null).map(_ => new Array(10).fill(0));
const divide = 1000000000;

function sol() {
  let answer = 0;

  for (let i = 1; i <= 9; i++) {
    dp[1][i] = 1;
  }
  for (let i = 2; i <= N; i++) { // 자릿수.
    for (let j = 0; j < 10; j++) { // 시작하는 숫자.
      if (j === 0)
        dp[i][j] = (dp[i - 1][j + 1]) % divide;      
      if (j === 9)
        dp[i][j] = (dp[i - 1][j - 1]) % divide;
      if (1 <= j && j <= 8)
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % divide;
    }
  }

  for (let i = 0; i <= 9; i++) {
    answer += dp[N][i];
  }

  return answer % divide;
}

console.log(sol());

특이사항

 DP는 항상..어렵...다...