[Algorithm] 백준 DP문제 - 계단 수(1562) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 DP 계단 수 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1562

1562번: 계단 수

 

1. 풀이 소스

 

import java.io.*;

public class Main {
    static final int MOD = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110
        for (int i = 1; i <= 9; i++) 
            dp[1][i][1 << i] = 1; // 1자리에서 k라는 수가 오는 경우 (0은 첫번째 자리에 올 수 없음)
        
        for (int t = 2; t <= n; t++) {
            for (int k = 0; k <= 9; k++) { // 2자리부터는 0 가능
                for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
                    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)
                    
                    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
                    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
                    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능
                
                    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
                }
            }
        }
        
        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i][(1 << 10) - 1] % MOD; // 비트마스크의 마지막인덱스 1 111 111 111 (모든 숫자 방문)
            sum %= MOD;
        }
        
        System.out.println(sum);
    }
}

 

2. 풀이 중점 사항

 

계단 수

 

계단 수의 DP 점화식은 다음과 같습니다.

dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k + 1] // n은 자리수, k는 n의 자리에 있는 숫자

예를 들어 xx7이 있다고 가정하겠습니다.

 

xx7은 두번째 자리 수(3 - 1)가 6(k - 1) 이거나 8(k + 1) 인 값이어야 합니다.   

x67은 첫번째 자리수가 (2 - 1)가 5(k - 1) 이거나 7(k + 1)인 값이어야 합니다.

 

즉, 현재 n 번째 자리에서 k라는 숫자가 오기 위해서는 n - 1 자리에서 k - 1 숫자가 있는 dp와 n - 1 자리에서 k + 1 숫자가 있는 dp를 더해야 합니다.

 

하지만, 0 과 9의 경우는 0은 올라가는 계단 수만, 9는 내려가는 계단 수만 존재하므로  하단의 점화식을 세울 수 있습니다.

if (k == 0) dp[t][k] += dp[t - 1][k + 1]; // k == 0 인 경우 올라가는 연산만 존재
else if (k == 9) dp[t][k] += dp[t - 1][k - 1]; // k == 9인경우 내려가는 연산만 존재
else dp[t][k] += dp[t - 1][k + 1] + dp[t - 1][k - 1]; // 둘 다 가능

 

비트 마스킹 

 

다음은 0 ~ 9 까지 모든 숫자가 등장하는 계단 수를 구해야 합니다.

이를 위해 비트마스킹을 활용할 수 있습니다.

 

비트마스킹은 이전 풀이에서 활용한 방법으로 1 ~ n까지 숫자가 있을 때 방문 처리를 비트형태로 표현하는 방법입니다.

1 << 3 을 쉬프트 하게되면  1000 이 나오는데, 0은 방문 X, 1은 방문 O을 의미하도록 할 수 있습니다.

가령 111은 1, 2, 3번을 모두 방문 했다는 의미로 해석할 수 있습니다.

 

long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110

따라서, 기존의 점화식에 비트마스킹으로 방문 처리를 하는 기능을 추가하였습니다.

 

for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)

    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능

    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
}

 

이후, nextVisited  = visited | (1 << k)의 비트 or 연산으로 방문 처리가 될 수 있도록 하였습니다.

1000  | 0100   => 1100 이므로 (1, 2 번 방문)

 

만약 visited = 111 111 111 이었고, k == 9여서

nextVisited = 111 111 111 | 1 000 000 000 => 1 111 111 111이 된다면,
이는 곧  모든 위치를 방문한 경우를 의미하게 됩니다.

 

이상으로 계단 수 자바 풀이를 마치도록 하겠습니다. !

감사합니다.!