[Java] 백준 1562번. 계단수 (골드1)

https://www.acmicpc.net/problem/1562

1562번: 계단 수

풀이방법 아이디어를 떠올리기 힘든 비트마스킹을 활용한 DP문제입니다.

 

계단수라는 것은 각 자리수의 차이가 1입니다.

즉 N-1자리의 마지막 자리가 X로 끝나는 계단수가 있다면 이 뒤에 X와 1 차이가 나는 숫자를 붙여서 N자리의 계단수를 만들 수 있습니다.

 

1자리의 계단수는 모두 9개로 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]입니다. (0으로 시작하는 수는 계단수가 아님)

2자리의 계단수는 1자리의 계단수에 1차이가 나는 숫자를 붙여서 만들 수 있고 마지막 자리의 숫자에 따라

10 - 0으로 끝남

21 - 1로 끝남

12 32 - 2로 끝남

23 43 - 3으로 끝남

34 54 - 4로 끝남...

이런 식으로 구분됨을 알 수 있습니다.

이때 위에서 얘기했던것처럼 0으로 끝나는 계단수는 이전 N-1자리에서 1로 끝난 계단수에 0을 붙여 만든 것이고 1로 끝나는 계단수는 0으로 끝나거나 2로 끝난 계단수에 1을 붙여 만든 것입니다.

(이번 경우에는 0으로 끝나는 1자리수 계단수가 존재하지 않습니다.)

 

이 방법을 N번 반복하면 우리는 X로 끝나는 N자릿수의 계단수를 구할 수 있습니다.

다만 문제에서는 0~9까지 10개의 숫자를 모두 사용한 계단수를 묻습니다.

따라서 해당 계단수에 어떤 숫자가 사용되었는지를 기억해야하는데, 개수와 상관없이 사용의 여부만 알면 되기 때문에 비트마스킹을 활용할수 있습니다.

 

이제 위의 아이디어를 구현하면 됩니다.

다만 N자리 계단수를 구하기 위해 필요한 N-1자리의 계단수를 고려하는것은 너무 복잡하기 때문에 N-1단계에를 완전탐색하며 이 값을 N자리 계단수로 누적합해주는 식으로 코드를 짜는게 더 간단합니다.

그리고 조건으로도 주어졌지만 진행 과정중에 변수의 범위를 넘는 경우를 막기 위해 누적될 때마다 주어진 값으로 mod 연산을 해야합니다.

 

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

public class q1562_BOJ_계단수 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int max = (1 << 10);
		int mod = 1_000_000_000;

		int[] bit = new int[10];
		for (int i = 0; i < 10; i++) {
			bit[i] = 1 << i;
		}

		int N = Integer.parseInt(br.readLine());
		int[][][] dp = new int[10][N + 1][max];

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

		for (int n = 1; n < N; n++) {
			for (int j = 1; j < max; j++) {
				dp[1][n + 1][j | bit[1]] = (dp[1][n + 1][j | bit[1]] + dp[0][n][j]) % mod;
				for (int i = 1; i < 9; i++) {
					dp[i - 1][n + 1][j | bit[i - 1]] = (dp[i - 1][n + 1][j | bit[i - 1]] + dp[i][n][j]) % mod;
					dp[i + 1][n + 1][j | bit[i + 1]] = (dp[i + 1][n + 1][j | bit[i + 1]] + dp[i][n][j]) % mod;
				}
				dp[8][n + 1][j | bit[8]] = (dp[8][n + 1][j | bit[8]] + dp[9][n][j]) % mod;
			}
		}

		int sum = 0;

		for (int i = 0; i < 10; i++) {
			sum = (sum + dp[i][N][max-1]) % mod;
		}

		System.out.println(sum);

	}
}