아이디어

• 정답은 숫자의 길이($i$), 현재 등장한 숫자들의 집합($S$), 그리고 마지막 자리의 숫자($j$)에 영향을 받는다.
• 이전 길이와 이전 길이의 숫자 집합, 마지막 자리에 따라 부분문제 관계가 성립한다.
  • $\begin{aligned} f(i, S, j) &= f(i-1, S - \{j\}, j-1) + f(i-1, S, j-1)\\&+ f(i-1, S - \{j\}, j+1) + f(i-1, S, j+1) \end{aligned}$
  • (단, $j < 0$이거나 $j > 9$이면 성립하지 않음)
  • 구하는 답은 $f(N,\{0, 1, ..., 9\}, *)$의 총합이다.
• 3차원 배열을 동적 테이블로 이용한 DP로 문제를 해결한다.
  • 각 변수는 수의 길이, 현재 등장한 숫자 집합의 bitmask, 그리고 마지막 자리의 숫자를 나타내도록 한다.
• 단, m의 j번째 비트가 0이라면 j가 등장하지 않았는데 마지막 자리의 숫자가 j였다는 뜻이므로 모순인 경우다. 이런 경우는 무시한다.
• 마지막으로, 모든 덧셈은 법 $1,000,000,000$에 대한 모듈로 덧셈이어야 함에 주의한다.
  • int 범위 내에서 처리하고 싶다면 overflow가 나지 않도록 연속으로 3개 숫자를 더해선 안 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	
	static int N, ans;
	static int[][][] memo;	// [len][flags][last_digit]

	static final int MOD = 1_000_000_000;
	static final int ALL = 0b11_1111_1111;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		memo = new int[N+1][ALL+1][10];

		// 0은 제외
		for(int i=1; i<=9; i++) {
			memo[1][1 << i][i] = 1;
		}
		
		for (int i=2; i<=N; i++) {
			for (int m=0; m<=ALL; m++) {
				for (int j=0; j<10; j++) {
					if ((m & 1 << j) == 0) continue;	// j-th bit is 0
					if (j < 9) {
						memo[i][m][j] = (memo[i][m][j] + memo[i-1][m & ~(1 << j)][j+1]) % MOD;
						memo[i][m][j] = (memo[i][m][j] + memo[i-1][m][j+1]) % MOD;
					}
					if (j > 0) {
						memo[i][m][j] = (memo[i][m][j] + memo[i-1][m & ~(1 << j)][j-1]) % MOD;
						memo[i][m][j] = (memo[i][m][j] + memo[i-1][m][j-1]) % MOD;
					}
				}
			}
		}
		
		for (int i=0; i<10; i++) {
			ans = (ans + memo[N][ALL][i]) % MOD;
		}
				
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 21888 KB
• 시간: 180 ms

리뷰

• m의 j번째 비트가 0일 때 모순이라는 생각을 떠올리기까지 상당히 오래걸렸다.
• 법을 10억이 아닌 100만으로 놓는 실수를 했었다.