문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제

예제 입력 1

1
2
1

예제 출력 1

1
2
9

예제 입력 2

1
2
2

예제 출력 2

1
17

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
];

while (DP.length !== input + 1) {
  DP.push([...Array(10)]);
}

for (let i = 2; i <= input; i++) {
  for (let j = 0; j <= 9; j++) {
    DP[i][j] = ((DP[i - 1][j - 1] || 0) + (DP[i - 1][j + 1] || 0)) % 1000000000;
  }
}

console.log(DP[input].reduce((acc, cur) => (acc + cur) % 1000000000, 0));
  • DP[i][j]의 값은 길이가 i인 수가 j(0~9)로 끝나는 모든 경우의 수이다.
  • DP 배열을 하드코딩으로 직접 만들어줬다. 왜나하면 초기값 같은 경우는 직접 만드는 편이 더 로직이 간편하기 때문이다. 이후 input의 길이보다 1 더 큰 길이로 DP 배열에 추가하였다.
    • 이렇게 하지 않으면 DP[input]의 값이 존재하지 않는 값이여서 값을 할당할 수가 없다.
  • 주어진 테케에서 길이가 1인경우, 길이가 2인 경우의 패턴을 파악하였다.
    • 예를 들어 DP[2][1]인 경우 길이가 2이고 1로 끝나는 경우의 수는 1 앞에 올 수 있는 수는 0,2이다. 이 값이 바로 DP[1][0]과 DP[1][2] 이다.
  • 저번 문제에서도 그렇고 왜 10억을 값을 저장할 때 한번, 총합을 구할 때 두번 나눠주는지 이해가 안된다.
  • 주의할 점은 끝나는 수가 0인 경우는 이전 숫자로 1만 올 수 있고, 끝나는 숫자가 9인 경우는 이전 숫자로 8만 올 수 있는 것을 고려해준 것이 바로 || 논리 연산자 부분이다.