문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
모든 숫자를 한 번 이상 사용해야 하므로, 현재 마지막 숫자뿐 아니라 지금까지 어떤 숫자를 사용했는지도 함께 상태로 가져가야 한다. 그래서 길이, 마지막 숫자, 사용한 숫자 비트마스크를 상태로 두는 DP가 필요하다.
한 자리씩 늘릴 때는 현재 마지막 숫자에서 -1 또는 +1로만 이동할 수 있다. 다음 숫자를 붙이면서 비트마스크에 해당 숫자를 켜 주면, 길이가 N이 되었을 때 모든 숫자가 켜진 상태만 정답 후보가 된다.
단순 계단 수 DP에 모든 숫자를 사용했는가라는 조건이 하나 더 붙은 형태라고 보면 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int MAX_VISIT = 1023;
static int MOD = 1000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
System.out.println(solve(N));
}
static long solve(int N) {
long[][][] dp = new long[N + 1][10][MAX_VISIT + 1];
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 = 1; k <= MAX_VISIT; k++) {
long prev = dp[i - 1][j][k];
if (prev != 0) {
if (j > 0) {
int next = k | (1 << (j - 1));
dp[i][j - 1][next] = (dp[i][j - 1][next] + prev) % MOD;
}
if (j < 9) {
int next = k | (1 << (j + 1));
dp[i][j + 1][next] = (dp[i][j + 1][next] + prev) % MOD;
}
}
}
}
}
long ans = 0;
for (int i = 0; i <= 9; i++)
ans = (ans + dp[N][i][MAX_VISIT]) % MOD;
return ans;
}
}복잡도
- 시간 복잡도: 길이, 마지막 숫자, 방문 비트마스크 상태를 갱신하므로 이다.
- 공간 복잡도: DP 배열을 저장하므로 이다.
마무리
계단 수 자체는 익숙하지만, 이번에는 어떤 숫자를 썼는지도 기억해야 한다. 마지막 숫자와 사용 집합을 함께 들고 가면 조건이 자연스럽게 녹아든다.
