해당 포스팅은 백준 10844번 쉬운 계단 수 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
인접한 모든 자리의 차이가 1
인 수 (EX. 45656)[첫째 줄]
: N (1 ≤ N ≤ 100)
[첫째 줄]
: 정답 % 1,000,000,000
N = 2일 때 가능한 계단수를 생각해보자.
10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98 가 있다.
해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이 정해진다.
일의 자리 수가 0
일 때 1차이가 날 수 있는 자연수는 오직 1뿐이다.
반면 2부터 8까지 자연수
는 자기 자신의 +1, -1인 숫자가 올 수 있다. 예시로 일의 자리 수가 8일 때 가능한 계단수는 78, 98이 있다.
일의 자리 수가 9
일 때 1차이가 날 수 있는 자연수는 오로지 8뿐이다.
이처럼 이전의 숫자들이 어떤 값인지에 따라 올 수 있는 답이 정해져있다. 즉 이전 자리수(부분합)을 먼저 구해야 하는 문제이므로 DP로 풀이
하면 된다.
N = 3일 때를 예시로 설명하겠다.
위의 표들을 보면 N이 3일 때 가능한 조합은 총 32개가 있다.
[N=1]일 때
1~9까지 각 자연수가 가능하다. 0은 자연수가 아니므로 불가능하다.
[N=2]일 때
[N=3]일 때
dp[2][1](210) + '0'
이다.dp[3][j] = dp[2][j-1] + dp[2][j+1]
임을 확인할 수 있다.dp[2][8](78, 98) + '9'
임을 확인할 수 있다.따라서 해당 로직을 점화식으로 표현하면 아래와 같다.
JS의 비교연산자를 이용해 위의 로직을 아래의 점화식으로 표현할 수 있다.
점화식
DP[i][j] = DP[i-1][j-1] || 0 + DP[i-1][j+1] || 0
(0 ≤ j ≤ 9)
const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);
const DP = new Array(N)
for (let i=0; i<N; i++) {
DP[i] = new Array(10).fill(0)
}
for (let i=1; i<=9; i++) {
DP[0][i] = 1;
}
for (let i=1; i<N; i++) {
for (let j=0; j<=9; j++) {
DP[i][j] = (DP[i-1][j-1] || 0) + (DP[i-1][j+1] || 0) % 1000000000;
}
}
const result = DP[N - 1].reduce((acc, curr) => {
return (acc + curr) % 1000000000;
}, 0);
console.log(result);