문제 이해
인접한 모든 자리의 차이가 1인 수를 계단수라고 한다.
이 때 N자리 계단 수 중 0 ~ 9까지 모두 등장하는 계단수의 개수를 구하는 문제이다.
(단, 0으로 시작하는 수는 계단수가 아니다)
문제 풀이
매우 특이한 문제였다.
계단수 자체를 파악하는 것은 매우 쉽다. 지금까지 했던 것처럼 현재 상황 직전 상황을 파악하여, 현재 N을 선택한다면 직전에 N-1이나 N+1인 경우를 확인하고 해당 부분에 저장되어 있는 값을 활용하여 현재 상황에 적용하면 되기 때문이다.
여기서 중요한 점은 '0~9까지 숫자가 모두 등장한다'라는 점이다. 즉, 우리는 DP를 위한 배열에 직전까지 만든 계단 수에서 활용한 숫자의 종류를 입력해야 된다는 것이다.
그런데, 배열을 N*10으로 만들면 문제가 생긴다.
만약, 내가 T번째에 3을 선택했다고 하자. 그렇다면 arr[T][3]에는 계단 수에서 활용한 숫자 종류가 입력될 것이다. 이때 arr[T-1][2]에 저장된 값을 활용해야 하는가 arr[T-1][4]에 저장된 값을 활용해야 하는가?
두 개의 값 모두 중요하기 때문에 모두 활용해야 할텐데, 이를 위해 배열의 원소를 List로 해버리면 너무 많은 시간 낭비가 발생하고 너무나 많은 공간 낭비가 발생할 것이다.(List를 Search해야하고, List를 위한 공간도 필요할 것이므로)
따라서, Index를 하나 추가해주고, 해당 index에 bitmask를 활용하여 활용한 숫자의 종류를 기억하는 방식을 사용했다.
예를 들어, ans[T][2][bitmask]일 경우, T번째에 2를 넣는 경우의 수를 구하는 것이다. 이 때, bitmask에는 T번째까지 만든 계단 수에서 활용한 숫자 종류가 저장되어 있을 것이다.
예를 들어 111일 경우, 0,1,2가 활용되었다는 것으로 인식할 수 있을 것이다.
우리는 0~9까지 중 한 개의 숫자를 활용할 수 있으므로 bitmask 공간은 총 1<<10 만큼 필요할 것이다.
마지막으로 ans[T][2]에는 해당 bitmask로 계단수를 형성할 수 있는 개수를 저장하여, 모든 경우의 수를 다 세는 방식을 활용하였다.
이 부분에 대해서는 코드로 설명하는 것이 쉽기 때문에 아래 코드에 자세한 설명을 첨부했다.
이 문제는 1 ~ T까지 계단수를 고정시킨 이후, T+1 ~ N까지 계단수를 마저 구한 이후 0~9를 모두 활용한 결과값을 활용하여 1 ~ T까지의 계단수 공간에 저장하는 방식을 사용한 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static long[][][] DP;
static final long MOD = 1000000000;
static long dp(int length, int before, int bitmask) {
// length : N자리 계단수를 위해 추가해야 하는 수의 남은 개수
// length = 0이 되는 순간 N자리 계단수를 만든 것이다.
if(length==0) {
// N자리 계단수가 만들어졌다.
if(bitmask==((1<<10)-1)) {
// 이 상황인 경우 0 ~ 9번째 자리에 모두 1이 설정되었다는 것이다
// 이는 0 ~ 9가 모두 활용되었다는 의미이므로 정답이기 때문에
// 1을 반환한다.
return 1;
}
// 아닐 경우 0 ~ 9 모든 수가 활용된 게 아니므로 0을 반환한다.
return 0;
}
if(DP[length][before][bitmask]!=0) {
// DP[length][before][bitmask]가 0이 아니라면
// 이미 계산이 수행되었다는 의미이다.
// 계산이 한 번 수행된 이후 다시 수행될 수가 없다.
return DP[length][before][bitmask];
}
// 현재 위치에는 before이 들어가 있다.
// 다음 위치에는 before-1이나 before+1이 들어가야 할 것이다.
long ans = 0;
if(before-1>=0) {
ans = dp(length-1, before-1, bitmask | (1<<(before-1)));
// before-1이 다음 위치에 들어갈 경우이다.
// 이 경우, before-1이 사용되었기 때문에 원래 bitmask에
// 1<<(before-1)을 추가해준다
}
if(before+1<10) {
ans += dp(length-1, before+1, bitmask | (1<<(before+1)));
// before+1이 다음 위치에 들어갈 경우이다.
// 이 경우, before+1이 사용되었기 때문에 원래 bitmask에
// 1<<(before+1)을 추가해준다
}
DP[length][before][bitmask] = ans % MOD;
// before 위치까지 계단 수를 만들었을 때, 만약 이 계단 수를 통해
// 끝까지 계단 수를 만들고 해당 계단 수가 0 ~9를 모두 포함한 경우의 수는
// ans에 더해졌을 것이다.
// 따라서, ans 값을 DP[length][before][bitmask]에 저장한다.
return ans;
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
N = sc.nextInt();
DP = new long[N][10][1<<10];
// DP[i][j][k]
// i,j : i번째 자리에 j를 입력하는 경우
// k : bitmask를 위한 공간. 현재까지 활용한 숫자들을 저장함
// 0 ~ 9를 위한 bitmask가 필요하므로 1<<10만큼의 공간이 필요
long ans = 0;
for(int i =1;i<10;i++) {
ans+=dp(N-1,i,1<<i);
ans%=MOD;
}
System.out.println(ans);
}
static class FastReader // 빠른 입력을 위한 클래스
}
결과
