b.1562 계단수

 

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

 

 

 

이 문제는 어떠한 수 N 이 주어졌을 때 각자리수를 이동할때마다 1 씩 차이나는

수를 계단수로 정의하고 N의 자릿수를 가지며 0~9 까지 모든 수가 등장하는 계단 수의

갯수를 구하는 문제이다.

 

처음 문제를 마주했을때 문제를 이해하지 못했다. DP를 활용해야하며 비트마스킹을

활용해야한다는 팁을 보고서도 문제를 풀이할 방법을 찾지 못했다.

 

dp 3차원 배열을 활용, 비트마스킹을 활용한 방법을 설명 하겠다.

dp[][][] 3차원배열의 각 차수에는 

첫째 몇번째 자리수 인지 i 

둘째 마지막 숫자가 무엇인지 j

셋째 그 숫자의 check 상태는 어떠한지(비트마스킹)

을 활용한다.

 

dp 는 초기 설정, 점화식 이 제일 중요하다고 본다.

 

초기설정은 dp 의 1번째 자리수, 마지막 숫자를 기준으로 체크상태를 변경해주며 1로 초기화

한다. 즉, 

dp [0][1~9][1 <<  i] =  1; 

을 수행해주면 0번째 자리수(필자는 1번째 자리수를 위해 N+1 하지 않았다. N-1로 계산함)

의 마지막 숫자 1~ 9 마다 비트를 켜주고 1로 초기화 해주면  초기설정이 끝난다.

 

점화식은 이렇게 세운다.

i = 0 과 i = 9 라면 -1 과 10 은 계단수에 해당되지 않기때문에
dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j-1][k])%MOD; (i = 9일때)
dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j+1][k])%MOD;  (i = 0일때)

그외에는

dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j+1][k] + dp[i-1][j-1][k])%MOD;
이렇게 적용한다.

최종적으로 dp[n-1]에 bit가 [1023]으로 체크되어있는 0에서 9까지의 모든 숫자를 더하고
MOD 연산을하여 출력하여 문제를 해결하였다.

 

 

 

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

public class b1562 {

    static int n, MOD = 1000000000;
    static long[][][] dp ;

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

        n = Integer.parseInt(br.readLine());
        dp = new long[n][10][1024];

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

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

        long answer = 0;
        for(int i = 0 ; i < 10 ; i++){
            answer += dp[n-1][i][1023];
            answer %= MOD;
        }
        System.out.println(answer);
    }
}