자바 - 백준 1562 / 계단 수

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

골드1

 

구현 방법

길이가 N인 계단수를 구하는 방법은 길이가 (N-1)인 계단수에서 하나의 숫자를 추가해 주면 된다.

이때 (N-1)인 계단수의 마지막 수에서  + 1이거나 - 1인 수를 하나 추가하면 만들어진다.

그럼 이제 계단수를 구하기 위해 필요한 정보를 알수 있다.

계단수 길이, 현재 계단수의 마지막 자리수가 필요하게 된다.

하지만 문제 조건에서 0~9 모든 수가 나와야 한다고 했으므로, 현재 만들어진 계단수도 필요하게 된다.

또한 완전 탐색할 경우 9^N개의 경우의 수가 나오므로 시간초과 가능성이 매우 높다.

따라서 전의 계단수로 현재 계단수를 구하기 때문에 "다이나믹 프로그래밍"을 이용하기로 했다.

이때 현재 만들어진 계단수는 비트마스크를 이용하기로 했다. 이를 이용하면 현재 자리수에 있는 숫자를 나타내기 편하고 속도도 빠르기 때문이다.

 

따라서 점화식을 구하면 다음과 같다.

i: 계단 수의 길이 (1부터 N까지)
j: 현재 계단 수의 마지막 숫자 (0부터 9까지)
k: 등장한 숫자들의 비트마스크 (0부터 9까지 각 숫자의 등장 여부를 10비트로 표현)

dp[i][j][k | (1 << j)] = dp[i-1][j-1][k] + dp[i-1][j+1][k]

코드

import java.io.*;

/**
 * 백준 1562
 * 계단 수
 * 골드 1
 * https://www.acmicpc.net/problem/1562
 */
public class Boj1562 {

    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];

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

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k < (1 << 10); k++) {
                    if(j > 0) {
                        dp[i][j][k | (1 << j)] =
                                (dp[i][j][k | (1 << j)] +
                                        dp[i - 1][j - 1][k]) % MOD;
                    }

                    if(j < 9) {
                        dp[i][j][k | (1 << j)] =
                                (dp[i][j][k | (1 << j)] +
                                        dp[i - 1][j + 1][k]) % MOD;
                    }
                }
            }
        }

        long answer = 0;
        int full = (1 << 10) - 1;
        for(int i = 0; i < 10; i++) {
            answer = (answer + dp[N][i][full]) % MOD;
        }

        System.out.println(answer);
        
    }
}

 

느낀점

디피 문제들은 점화식을 떠올리기가 너무 어렵다.

이 문제는 점화식은 떠올랐는데 현재까지 구한수를 어떤 방식으로 저장할지 생각하는 과정이 매우 어려웠다

비트마스킹에 익숙해지면 굉장히 좋을듯!