[백준 #1562] 계단 수 - JAVA [자바]

분류

비트마스킹, 다이나믹 프로그래밍, 비트필드를 이용한 다이나믹 프로그래밍

 

문제 설명

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입력

10

 

예제 출력

1

 

코드 - 계단 수.java

import java.util.Scanner;

public class Main {
    static int mod = 1000000000;
    static int[][][] dp = new int[101][10][1024];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        // Initialize for length 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 = 0; k < 1024; k++){
                    if(j == 0){
                        dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k];
                    } else if(j == 9){
                        dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k];
                    } else {
                        dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k];
                        dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k];
                    }
                    dp[i][j][k | (1 << j)] %= mod;
                }
            }
        }

        int sum = 0;
        for(int i = 0; i <= 9; i++){
            sum = (sum + dp[n][i][1023]) % mod;
        }
        System.out.println(sum);
    }
}

 

코드 분석하기

1. static int mod = 1000000000; static int[][][] dp = new int[101][10][1024];
    이 문제에서는 동적 프로그래밍(DP)을 사용합니다. 이는 복잡한 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. dp 배열은 이 문제에서의 하위 문제의 결과를 저장하는 역할을 합니다. dp[i][j][k]는 i개의 숫자를 가지고 있고, 마지막 숫자가 j이며, 사용된 숫자의 집합이 k일 때의 계단 수의 개수를 나타냅니다. mod는 문제에서 요구하는 대로 결과를 1,000,000,000로 나눈 나머지를 구하기 위해 사용되는 변수입니다.
   
2. for(int i = 1; i <= 9; i++){ dp[1][i][1 << i] = 1; }
    이 부분은 DP 배열의 초기 상태를 설정하는 부분입니다. 첫 번째 숫자(1~9)가 사용된 경우에 대해 1로 설정합니다. 이때 비트 마스킹을 이용하여 사용된 숫자를 표시하고 있습니다. **1 << i**는 i번째 비트를 1로 만들어 줍니다. 즉, i번째 숫자가 사용되었음을 나타내는 것입니다.
   
   
3. for(int i = 2; i <= n; i++){...}
    이 부분은 입력받은 숫자의 개수(n)만큼 반복하면서 DP 배열을 채워나가는 과정입니다. 이 부분에서는 각 숫자(0~9)에 대해 그 숫자가 마지막에 사용된 숫자라면, 이전 숫자는 그보다 1 작거나 1 큰 숫자일 것입니다. 그래서 이를 기반으로 dp[i][j][k]를 채워나갑니다.
   
   
4. if(j == 0){ dp[i][j][k | (1 << j)] += dp[i - 1][j + 1][k]; } else if(j == 9){ dp[i][j][k | (1 << j)] += dp[i - 1][j - 1][k]; } else {...}
    이 부분은 계단 수의 규칙(인접한 자리의 차이가 1)을 적용하여 이전 상태에서 현재 상태로의 변화를 구하는 부분입니다. 마지막 숫자가 0이라면 다음 숫자는 1, 마지막 숫자가 9라면 다음 숫자는 8이 됩니다. 이외의 경우에는 마지막 숫자가 1 증가하거나 1 감소하는 경우가 가능합니다. **k | (1 << j)**는 비트 마스킹을 이용해 j번째 숫자가 사용되었음을 나타냅니다. 이는 이전 상태에서 j번째 숫자를 추가하는 경우를 계산하는 것입니다.
   
   
5. dp[i][j][k | (1 << j)] %= mod;
    이 부분은 dp의 값을 mod로 나눈 나머지로 유지해주는 부분입니다. 이는 문제에서 요구하는 대로 결과를 1,000,000,000로 나눈 나머지를 구하기 위함입니다.
   
   
6. for(int i = 0; i <= 9; i++){ sum = (sum + dp[n][i][1023]) % mod; }
    이 부분은 모든 계단 수를 합산하는 부분입니다. 길이가 n이고 모든 숫자를 사용한 계단 수는 dp[n][i][1023]에서 구할 수 있습니다. 모든 숫자를 사용하면 1023 (1111111111 in binary)이 됩니다. 그래서 이 값을 모든 i에 대해 합산하면 원하는 결과를 얻을 수 있습니다.
   
   

코드에서 사용된 주요 개념:

1. 비트마스킹: 비트 연산을 이용해 특정 비트들의 상태를 나타내는 기법입니다. 이 문제에서는 어떤 숫자가 사용되었는지를 나타내기 위해 비트 마스킹을 사용합니다.
2. 다이나믹 프로그래밍: 복잡한 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. 이 문제에서는 DP를 이용해 n개의 숫자를 가지는 계단 수를 구합니다.
3. 비트필드를 이용한 다이나믹 프로그래밍: 비트 필드는 비트마스킹과 비슷하게 비트 연산을 이용해 여러 상태를 나타내는데 사용됩니다. 이 문제에서는 dp[i][j][k]에서 k에 비트 필드를 사용하여 각 숫자의 사용 여부를 저장합니다. 이렇게 비트 필드를 이용하면 여러 개의 boolean 변수를 사용하는 것보다 메모리 효율성이 좋습니다.

 

 

백준에서 문제 풀어보기

 

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

1562번: 계단 수