백준 11057번: 오르막 수 - javascript

백준 11057번: 오르막 수

문제 설명

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

접근

먼저 n의 오르막 수 갯수끼리는 연관관계를 찾기 어려워보인다.. 그러면 각 자릿수로 찾는게 쉽지 않을까? 라고 생각했다. 위의 설명에서 0부터 시작 할 수 있다라고 했다. 즉, 어떤 자릿수든 0부터 9까지의 경우가 주어진다는 뜻이다. 직접 경우를 나열해 봤는데 n이 3부터 슬슬 윤곽이 보이기 시작했다.

n이 2일 경우를 생각해보자. 0으로 시작할 경우 00 부터 09까지 나타낼수 있다. 1으로 시작하면 11 부터 19까지 그렇게 쭉 진행하면 8은 88과89, 9는 99밖에 안된다.

이제 n이 3인 경우를 생각해보자. 0으로 시작할 경우 000 부터 099까지 나타낼 수 있다. 그런데 어딘가 익숙하지 않은가?
바로 위의 n이 2일경우에 수가 보인다. 0+00 ~ 0+99, 즉 3자리수에서 0으로 시작하는 경우의 수는 2자리수의 모든 경우의 수와 같다.
그럼 1은? 1+11 ~ 1+99, 2자리수에서 1부터 9까지의 경우의 수의 합과 같다.
이걸 좀 더 알아보기 쉽게 표로 나타내면 아래와 같다.

이제 우리는 구하고자 하는 i자리 값의 각 자리값에 대해 다음과 같은 공식을 얻을 수 있다.

    arr[i][0] = (arr[i-1][0] + arr[i-1][1] + arr[i-1][2] + arr[i-1][3] + arr[i-1][4] + arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][1] = (arr[i-1][1] + arr[i-1][2] + arr[i-1][3] + arr[i-1][4] + arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]); 
    arr[i][2] = (arr[i-1][2] + arr[i-1][3] + arr[i-1][4] + arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][3] = (arr[i-1][3] + arr[i-1][4] + arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][4] = (arr[i-1][4] + arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][5] = (arr[i-1][5] + arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][6] = (arr[i-1][6] + arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][7] = (arr[i-1][7] + arr[i-1][8] + arr[i-1][9]);
    arr[i][8] = (arr[i-1][8] + arr[i-1][9]);
    arr[i][9] = (arr[i-1][9]); 

으윽… 짜고 보니 너무 더럽다..

좀 더 생각해보니깐 n번째의 1로 시작하는 경우의 수는 n-1번째에서 0으로 시작하는 수를 제외한 1부터 9로 시작하는 수들의 합이다.
그러면 n번째의 0으로 시작하는 경우의 수는 n-1번째에서 0부터 9로 시작하는 수들의 합이니깐 다르게 표현하면 n번째의 1으로 시작하는 경우의 수와 n-1번째의 0으로 시작하는 수의 합이 될 수 있지 않을까?

위의 그림과 같은 식으로 위에 썼던 코드를 다시 쓰면…

    arr[i][9] = (arr[i-1][9]);
    arr[i][8] = (arr[i][9] + arr[i-1][8]);
    arr[i][7] = (arr[i][8] + arr[i-1][7]);
    arr[i][6] = (arr[i][7] + arr[i-1][6]);
    arr[i][5] = (arr[i][6] + arr[i-1][5]);
    arr[i][4] = (arr[i][5] + arr[i-1][4]);
    arr[i][3] = (arr[i][4] + arr[i-1][3]);
    arr[i][2] = (arr[i][3] + arr[i-1][2]);
    arr[i][1] = (arr[i][2] + arr[i-1][1]);
    arr[i][0] = (arr[i][1] + arr[i-1][0]);

훨씬 나아졌다!

이런 방식을 이용하면 출력할 때도 n번째의 0으로 시작하는 경우부터 9로 시작하는 경우까지의 합을 반환해줄 필요없이 n+1번째의 0으로 시작하는 경우의 수 만 반환 해주면 된다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let n = input[0]*1;
  
  let answer = orum(n);
  console.log(answer)
  process.exit();
});

function orum(n){
  let arr = [];
  for(let i =0;i<=n;i++){
    arr.push([0,0,0,0,0,0,0,0,0,0])
  }
  arr[0] = [1,1,1,1,1,1,1,1,1,1];
  if(n==1)return 10;
  for(let i=1;i<=n;i++){    
    arr[i][9] = (arr[i-1][9])%10007;
    arr[i][8] = (arr[i][9] + arr[i-1][8])%10007;
    arr[i][7] = (arr[i][8] + arr[i-1][7])%10007;
    arr[i][6] = (arr[i][7] + arr[i-1][6])%10007;
    arr[i][5] = (arr[i][6] + arr[i-1][5])%10007;
    arr[i][4] = (arr[i][5] + arr[i-1][4])%10007;
    arr[i][3] = (arr[i][4] + arr[i-1][3])%10007;
    arr[i][2] = (arr[i][3] + arr[i-1][2])%10007;
    arr[i][1] = (arr[i][2] + arr[i-1][1])%10007;
    arr[i][0] = (arr[i][1] + arr[i-1][0])%10007;
  }
  return arr[n][0]%10007;
}