[백준1526_자바스크립트(javascript)] - 계단 수

🔴 문제

계단 수

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const n = +fs.readFileSync(path).toString();
const dp = Array.from({ length: n + 1 }, () => Array.from({ length: 10 }, () => Array(1 << 10).fill(0)));
const mod = 1000000000;

for (let i = 1; i < 10; i++) {
  dp[1][i][1 << i] = 1;
}

for (let i = 2; i <= n; i++) {
  for (let j = 0; j <= 9; j++) {
    for (let k = 0; k < 1 << 10; k++) {
      if (j > 0) dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k];
      if (j < 9) dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k];

      dp[i][j][k] %= mod;
    }
  }
}

let ans = 0;
for (let i = 0; i <= 9; i++) {
  ans += dp[n][i][(1 << 10) - 1];
}

console.log(ans % mod);

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 쉬운 계단 수 의 어려운 버전이다.

계단 수를 찾는다는 점은 비슷하지만, 계단 수 중 0부터 9까지의 모든 숫자를 적어도 한 번씩 포함하는 계단 수를 찾아야 하는것이 특징이다.

0부터 9까지의 숫자가 모두 포함되었는지, 아닌지는 비트연산으로 빠르게 확인할 수 있다. 즉 dp + 비트연산 유형의 문제다.

dp 배열 dp[n][k][mask]은 아래와 같이 정의된다.

• 길이가 n개이며 k로 끝나는 계단 수
• mask은 0부터 9까지의 수 중 어떤 수가 포함되었는지를 확인하는 비트값
• 0~9까지 총 10자리므로 2의 10승인 1024 즉 1 << 10의 크기를 가진다.

for (let i = 1; i < 10; i++) {
  dp[1][i][1 << i] = 1;
}

위 코드를 살펴보자 dp에 초기값을 세팅하는 로직이다.
한 자리수이면서 0이 아닌 숫자만 가능하므로, 길이가 1일 때 1부터 9까지만 초기화 해준다.
그리고 각 계단 수는 i 하나만 포함하고 있으니 1 << i의 값을 1로 두는 것이다.

for (let i = 2; i <= n; i++) {
  for (let j = 0; j <= 9; j++) {
    for (let k = 0; k < 1 << 10; k++) {
      if (j > 0) dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k];
      if (j < 9) dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k];

      dp[i][j][k] %= mod;
    }
  }
}

이제 dp 배열을 채워줘야 한다. 길이가 1인 계단 수는 채웠으니 i는 2부터 n까지, j는 0부터 9까지 k는 0부터 1 << 10까지 반복해주면 된다.
이전 자리수에서 인접한 수만 올수 있다는 조건을 만족하기 위해 조건문을 걸어준 뒤, 비트연산을 통해 현재 숫자 j가 사용되었음을 마스팅해주면 된다.

정답은 최종 자리수가 n이고, 마지막으로 끝나는 수가 0~9인 경우에서 1 << 10 -1을 통해 모든 수를 가지고 있는 계단수의 개수만 세어주면 된다.

🔵 Ref

[백준10844_자바스크립트(javascript)] - 쉬운 계단 수