백준 1562번 : 계단 수 [Java]

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

문제 탐색하기

문제에서 요구하는건 특정 조건을 만족하는 계단 수를 구하는 것이다.

• 0 ~ 9까지의 모든 수를 포함해야하며
• 인접한 모든 자리의 차이가 1이어야 한다.
• 계단 수는 0으로 시작할 수 없다.

문제를 시작하기 탐색하기 전에 비트필드를 이용한 DP 문제가 처음이라서 검색 시간이 있었다.

 

간단하게 설명하자면 비트가 켜진 유무에 따라서 수의 상태를 나타낼 수 있다.

0 ~ 9 까지의 모든 수를 포함하게 하려면 결국 직접 탐색을 하는 방법 밖에 없는데, 이 때 탐색을 진행하다가 특정 수를 만나면 해당 비트를 키는 방식으로 진행하면 된다.

 

설명을 위해 비트필드를 배열로 표현하였다. 아래와 같은 비트필드를 이용해서 계단수를 탐색하면서 1을 만났다고 가정하면 1번 자리에 해당하는 비트를 키면 된다.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

//숫자 0을 찾은 경우

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

 

이를 코드로 옮긴다고 치면 찾은 자리 수 만큼 << 연산을 통해 옮기고 원래의 비트필드 값과 | 연산를 통해서 해당 비트를 켜주면 될거 같다.

 

이제 점화식을 찾아보자

N = 1 ~ 9까지일 때는 0 ~ 9 까지의 모든 수를 포함할 수 없으므로 이들은 모두 0이라고 볼 수 있다. 하지만 앞의 수들을 비트 체크 해놓아야 하므로 우리가 dp에서 포함시켜야 할 항목들은 총 세가지 이다. 자리 수, 그 다음 숫자, 비트 필드를 포함하여 배열을 만들어야 한다

 

점화식을 구해보면 

• 앞의 숫자가 0일 때 : 다음 자리 수는 무조건 1이 되어야 한다.
• 앞의 숫자가 1 이상 8 이하일 때 : 다음 자리 수는 절댓값 차이가 1인 수가 되어야 한다.
• 앞의 숫자가 9일 때 다음 자리 수는 8이어야 한다.

따라서 현재 인덱스를 i, 사용한 숫자를 j, 비트필드를 k라고 한다면 다음과 같은 식이 성립한다.

 

// 0일 때
dp[i + 1][j + 1][k | 1 << (j + 1)] += dp[i][j][k]

// 9일 때
dp[i + 1][j - 1][k | 1 << (j - 1)] += dp[i][j][k]

// 1 이상 8 이하일 때 
// 0일 때와 9일 때를 모두 계산하면 된다.

 

코드 설계하기

1. 먼저 DP 값이 담길 배열을 설정한다. 이 때 배열은 3차원 배열로 구성한다. 

2. 첫번째 자리 수 부터 세기 위해 1로 초기화한다. 이 때 0으로 시작하는 수를 제외하기 위해서 0은 제외한다.

3. 앞서 설계한 점화식 대로 반복문을 통해 계산하고 나머지를 구해서 저장한다.

 

풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
    
    static int[][][] dp;
    static final int modular = (int)1e9;
    static final int bitField = 1 << 10;
    
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        int n = fr.nextInt();
        
        dp = new int[n + 1][10][bitField];
        
        for (int i = 0; i < 10; i++) {
            dp[1][i][1 << i] = 1;
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < bitField; k++) {
                    if (j != 9) {
                        dp[i + 1][j + 1][k | 1 << (j + 1)] += dp[i][j][k];
                        dp[i + 1][j + 1][k | 1 << (j + 1)] %= modular;
                    } 
                    if (j != 0) {
                        dp[i + 1][j - 1][k | 1 << (j - 1)] += dp[i][j][k];
                        dp[i + 1][j - 1][k | 1 << (j - 1)] %= modular;
                    }
                } 
            }
        }
        
        int answer = 0;
        for (int i = 1; i < 10; i++) {
            answer = (answer + dp[n][i][bitField - 1]) % modular;
        }
        System.out.println(answer);
    }
}