[백준] 1562. 계단 수

문제 링크

[백준] 1562. 계단 수

풀이 과정

다이나믹 프로그래밍 문제입니다.

let dp = Array.from(Array(10), () => Array.from(Array(N + 1), () => Array(1 << 10).fill(-1)));

dp[i][j][k] 는 계단수의 길이가 j이며, 마지막 수가 i로 작성이 되었으며, k에 담겨있는 수들을 사용했을 때의 계단 수의 개수를 의미합니다. k는 0부터 1023까지 가능하며, 이는 0부터 9까지 숫자의 사용 유무를 비트마스킹으로 표현한 것입니다.

예를 들어, N이 10일 때 0부터 9까지 모든 숫자가 자리수로 등장하는 계단 수는 위와 같이 한 가지입니다. 즉, dp[0][10][1023] 은 1이 됩니다.

for (let i = 1; i <= 9; i++) {
    init();
    answer += go(i, 1, 1 << i);
    answer %= MOD;
}

먼저, init()을 통해 dp 배열의 모든 요소 값을 -1로 초기화합니다. 그 이유는 다음과 같습니다. 예를 들어, dp[0][11][1023] 이 2라고 가정하면, 이는 길이가 11인 계단 수를 이루는 마지막 수가 0이라는 정보를 갖을 뿐, 그 앞 1에서 9까지의 숫자들이 어떤 순서로 등장한 지 모르기 때문입니다.

첫 자리에 0이 올 수 없으니, 0을 제외한 1부터 9까지를 맨 앞 숫자로 작성해 go()를 호출해 계단수를 구합니다. answer가 10억을 넘어갈 수 있으니, 10억을 나눈 나머지를 저장해 10억 미만이 되도록 유지합니다.

function go(now, length, used) {
    if (length === N) {
        return used === (1 << 10) - 1 ? 1 : 0;
    }

    if (dp[now][length][used] !== -1) {
        return dp[now][length][used];
    }

    let ret = 0;

    if (now - 1 >= 0) {
        ret += go(now - 1, length + 1, used | (1 << (now - 1)));
    }

    if (now + 1 <= 9) {
        ret += go(now + 1, length + 1, used | (1 << (now + 1)));
    }

    ret %= MOD;

    return (dp[now][length][used] = ret);
}

go()는 now, length, used를 파라미터로 받아, dp[now][length][used]에 계단 수를 누적합니다.

• 문제 조건에 따라 계단 수의 길이가 N이 되면, 0부터 9까지의 수를 모두 사용했는지 비교하고 모두 사용했으면 1을, 모두 사용하지 않았으면 0을 리턴합니다. 1은 계단 수가 만들어졌음을, 0은 계단 수가 아님을 의미합니다.
• 요소 값이 -1이 아니라면, 이전에 계단 수가 충족되었던 적이 있음을 나타내므로, 메모이제이션 된 값을 가져다 사용하기 위해 바로 리턴합니다.
• 요소 값이 -1이면, 해당 파라미터 값들로 재귀를 계속 진행해 계단 수를 만들어 보는 작업을 거쳐야 합니다. now 를 기준으로 1을 빼고 더하며, 그 값이 0에서 9를 충족한다면 재귀를 진행합니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux" ? fs.readFileSync("/dev/stdin") : `10`).toString().trim().split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

let N = +input();
let dp = Array.from(Array(10), () => Array.from(Array(N + 1), () => Array(1 << 10).fill(-1)));
const MOD = 1e9;
let answer = 0;

for (let i = 1; i <= 9; i++) {
    init();
    answer += go(i, 1, 1 << i);
    answer %= MOD;
}

console.log(answer);

function go(now, length, used) {
    if (length === N) {
        return used === (1 << 10) - 1 ? 1 : 0;
    }

    if (dp[now][length][used] !== -1) {
        return dp[now][length][used];
    }

    let ret = 0;

    if (now - 1 >= 0) {
        ret += go(now - 1, length + 1, used | (1 << (now - 1)));
    }

    if (now + 1 <= 9) {
        ret += go(now + 1, length + 1, used | (1 << (now + 1)));
    }

    ret %= MOD;

    return (dp[now][length][used] = ret);
}

function init() {
    for (let i = 0; i < dp.length; i++) {
        for (let j = 0; j < dp[i].length; j++) {
            for (let k = 0; k < dp[i][j].length; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
}