문제
45656처럼 인접한 숫자가 1씩 차이 나는 수를 계단 수라 한다. 길이가 N이면서 0~9까지 모든 숫자가 한 번 이상 등장하는 계단 수의 개수를 구하라. (단, 0으로 시작하는 수는 계단 수가 아니다.) 정답은 1,000,000,000으로 나눈 나머지를 출력한다.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 | 10 |
풀이
비트마스크 DP를 사용한다. dp[i][j][k]를 "길이가 i이고, 마지막 숫자가 j이며, 사용한 숫자 집합이 k인 계단 수의 개수"로 정의한다.
- 초기화: 길이 1인 계단 수는 1
9 각각 하나씩 (9)dp[1][i][1 << i] = 1, i가 1 - 점화식: 길이 i, 마지막 숫자 j인 계단 수는 이전 단계의 j-1 또는 j+1로 끝나는 계단 수에서 전이
- j == 0이면 j+1에서만 전이
- j == 9이면 j-1에서만 전이
- 그 외: j-1과 j+1 모두에서 전이
- 전이할 때 현재 숫자 j를 비트마스크 k에 OR 연산으로 추가
- 최종 답:
dp[N][0..9][(1<<10)-1]의 합 (모든 숫자가 포함된 경우) - 결과를 1,000,000,000으로 나눈 나머지 출력
핵심 아이디어: 비트마스크로 사용된 숫자 집합(0~9, 10비트)을 DP 상태로 표현하여 모든 숫자가 포함된 계단 수의 수를 효율적으로 계산한다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day152BOJ1562비트마스킹DP { // 1562
static final int MOD = 1_000_000_000;
static int N;
static long[][][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dp = new long[N + 1][10][1 << 10];
for (int i = 1; i <= 9; i++)
dp[1][i][1 << i] = 1;
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k < 1 << 10; k++) {
if (j == 0) {
dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % MOD;
} else if (j == 9) {
dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % MOD;
} else {
dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k] + dp[i - 1][j - 1][k])
% MOD;
}
}
}
}
long answer = 0;
for (int i = 0; i <= 9; i++)
answer += dp[N][i][(1 << 10) - 1];
System.out.println(answer % MOD);
br.close();
}
}복잡도
- 시간: O(N × 10 × 2^10)
- 공간: O(N × 10 × 2^10)