[JS][백준]11057_오르막 수

문제 번호

11057번: 오르막 수

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 풀이

 DFS를 사용해서 풀이를 진행하려고 하였으나 그랬다면 시간초과에 걸렸을것이다. '1000자리' 수 까지 확인을 해야하기 때문이다. 그래서 2차원 배열을 사용한 DP로 풀이를 진행하였다.

 

 우선 0으로시작하는 1자리 오르막수들부터 생각해본다. 당연히 '0' 1개 뿐이다. 

그럼 0으로 시작하는 2자리 오르막수를 생각해본다. 00, 01, 02, 03............ 09 까지 모두 1개가 존재한다.

그럼 0으로 시작하는 3자리 오르막수도 생각해보자. 000, 001, 002, ................ 099 까지 있을것이다. 모두 55개이다.

 

 손으로 표를 만들어서 써보다보니 N 자리 다음 N+1 자리의 0으로 시작하는 오르막수의 개수는 N자리에서 0,1,....9 로 시작 하는 숫자들의 합이라는것을 알 수 있었다. 즉 1자리(N) 오르막수중에 '0으로 시작하는 오르막수 + 1로 시작하는 오르막수 + ... 9로 시작하는 오르막수' = 10 이라면, 2자리 오르막수(N+1)중 0으로 시작하는 오르막수는 10개 라는뜻이다. 

 그리고 그 다음 '1로 시작하는 오르막수의 개수는, N+1자리의 '0'으로 시작하는 오르막수의 개수 - (N)자리의 '0'으로 시작하는 오르막수의 개수' 였다. 식으로 정리해보면 arr[j][i] = (arr[j-1][i] = arr[j-1][i-1]) 이다. 

 

1자리

2자리

3자리

...

...

N자리

0시작	1	10	55	220(빨간색들의 합)	초록색들의 합
1시작	1	9	45	윗칸 - 왼쪽대각선윗 칸 // (220 - 55)
2시작	1	8	...	...
3시작	1	7	...	...
4시작	1	6	...	...
5시작	1	5	...	...
6시작	1	4	...	...
7시작	1	3	...	...
8시작	1	2	...	...
9시작	1	1	...	...

N === 4 일때.

 

 문제에서 10007을 mod 값으로 사용하라고 했으므로 연산을 진행할때마다 mod 연산을 해주었다.

 

전체코드

const N = +require('fs').readFileSync('input.txt').toString().trim().split('\n');

function sol() {
  let answer = 0;
  const mod = 10007;

  let arr = new Array(10).fill(null).map(_ => new Array(N + 1).fill(0));
  let sum = 0;

  for (let i = 1; i <= 1; i++) { // 자리수
    for (let j = 0; j < 10; j++) { // 시작숫자.
      arr[j][i] = 1;
      sum += arr[j][i];
    }
  }

  for (let i = 2; i <= N; i++) { // 자리수
    for (let j = 0; j < 10; j++) { // 시작숫자
      if (j === 0) {
        arr[j][i] = sum % mod;
      } else {
        arr[j][i] = (arr[j - 1][i] - arr[j - 1][i - 1] + mod) % mod;
        sum += arr[j][i] % mod;
      }
    }
  }
  
  console.log(arr)

  for (let i = 0; i < 10; i++) {
    answer += arr[i][N] % mod;
  }

  console.log(answer % mod);
}
sol();

 

 

특이사항

(A + B) MOD C는(( A MOD C) + (B MOD C)) MOD C