문제

아이디어

너무나도 DP스러운 문제였다.
DP 풀이를 유도하기 위해서 Top-Down으로 생각해보았다.

N 자리의 계단수는 아래를 만족한다.

1. N자리의 계단수의 마지막 숫자를 제외한 N-1 자리의 숫자 또한 계단수이다.
2. 0~9까지의 숫자가 하나 이상 포함된다. 이 때, 0으로 시작되는 수는 유효하지 않다.

0~9 자연수의 상태를 저장하기 위해서 비트마스킹을 떠올리는 건 어렵지 않았고, 3차원 배열 dp[][][]를 선언하여 풀이했다. 각 차원이 의미하는 정보는 아래와 같다.

dp[I][J][K]

• I: 숫자의 길이를 의미한다.
• J: 계단 수의 마지막 숫자를 의미한다.
• K: 현재까지 사용한 숫자를 비트마스킹으로 저장한다.

예를 들어, dp[5][5][0b0000011111]는 마지막 숫자는 5이며, 1,2,3,4,5를 사용한 5자리 계단 수의 개수를 의미한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		final int MOD = 1000000000;

		// dp[I][J]K] => I길이의 계단 수, 끝자리는 J, 사용한 숫자는 K(비트)
		int[][][] dp = new int[101][10][1024];

		for (int i = 1; i <= 9; i++) {
			dp[1][i][1 << i] = 1;
		}

		for (int i = 1; i < 100; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 1024; k++) {
					if (dp[i][j][k] == 0)
						continue;
					if (j != 0) {
						dp[i + 1][j - 1][k | (1 << (j - 1))] += dp[i][j][k] % MOD;
						dp[i + 1][j - 1][k | (1 << (j - 1))] %= MOD;
					}
					if (j != 9) {
						dp[i + 1][j + 1][k | (1 << (j + 1))] += dp[i][j][k] % MOD;
						dp[i + 1][j + 1][k | (1 << (j + 1))] %= MOD;
					}
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < 10; i++) {
			ans += dp[N][i][1023];
			ans %= MOD;
		}

		System.out.println(ans);
	}
}

채점 결과

정답 코드와 제네레이터를 testcase.ac에 업로드하였다.