https://www.acmicpc.net/problem/1562
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
길이가 n인 계단수를 만들려면 길이가 n-1인 계단수 뒤에 마지막 수와 1 차이나는 수를 붙여주면 된다.
이를 메모이제이션 하기 위해서는 n x 10만큼의 배열을 만들어주면 된다.
하지만 이 문제에서는 0부터 9까지가 포함되었는지 체크해야 하므로n x 10 x (2^10)만큼의 배열이 필요하다.
그러한 배열 memo[len][num][state]는 길이가 len이고 1의 자리수가 num이며, state만큼의 숫자를 사용한 계단 수의 개수가 된다.
여기서 state란, 이진수 0000000000 ~ 1111111111 사이의 숫자를 의미한다.
왼쪽에서부터 9~0의 포함 유무를 나타내며 포함되면 1, 포함되지 않으면 0으로 표시된다.
0000000001(=십진수 1)은 0만 포함된 숫자이고, 0000100100(=십진수 36)은 2와 5만 포함된 숫자이다.
DFS를 통해 len == n일 때 0~9까지의 숫자가 모두 포함되면 정답이 되는 계단 수가 1개 count되므로 1을 반환하고, 이전 상태에서 cnt를 더해주면서 배열의 값을 채운다.
이 때 다음으로 올 수는 num과 1만큼 차이나야 하므로 num-1이 오는 경우와 num+1이 오는 경우의 memo 값을 더해주면 된다.
코드
const n = +require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')[0];
const mod = 1000000000;
// memo[len][num][state] : 길이가 len이고 1의 자리수가 num이며, 사용한 숫자가 state인 계단 수의 개수
const memo = Array.from(Array(n+1), () => Array.from(Array(10), () => Array(1 << 10).fill(-1)));
function solution(len, num, state) {
if (len == n) return state == (1 << 10) - 1 ? 1 : 0; // 0부터 9까지 모두 등장하는 계단 수이면 count
if (memo[len][num][state] > -1) return memo[len][num][state]; // 이미 방문한 경우
let cnt = 0; // 1만큼 차이나는 다음 수의 저장된 값
if (num - 1 >= 0) cnt += solution(len + 1, num - 1, state | (1 << (num - 1)));
if (num + 1 < 10) cnt += solution(len + 1, num + 1, state | (1 << (num + 1)));
return memo[len][num][state] = cnt % mod;
}
let result = 0;
for (let i=1; i<10; i++) { // 맨 앞자리에 0이 올 수 없으므로 1~9까지 탐색
result += solution(1, i, 1 << i);
result %= mod;
}
console.log(result);