[백준] 1562번 계단 수

문제 설명

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

문제 풀이

• 비트마스킹 + DP를 이용하여 풀이하였다.
• 문제에서 DP 최적 부분 구조를 구성할 때 메모이제이션 해야하는 요인은 다음 3가지이다.

  1. 현재 자리수
  2. 현재까지 0~9까지 숫자의 방문 여부
  3. 마지막 수

• 위를 만족하기 위하여 DP 점화식은 다음과 같이 구성한다.

  DP[현재 자리수][0~9방문여부(비트마스킹)][마지막 수]
  DP[ind][chk][last] =
  DP[ind-1][chk][last+1] + --------------> 마지막수 + 1
  DP[ind-1][chk - (2<<last)][last+1] + ---> 마지막수 + 1, chk에서 마지막수 없앰
  DP[ind-1][chk][last-1] + ---------------> 마지막수 - 1
  DP[ind-1][chk - (2<<last)][last=1] + ---> 마지막수 - 1, chk에서 마지막수 없앰

• 위 점화식에 기저조건을 적절히 설정하면 풀이 가능하다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, MOD = 1000000000, INF = 987654321;
    public static int[][][] dp;

    public static int dfs(int ind, int chk, int last) {
        //기저조건1 : 첫째자리인 경우
        if (ind == 1) {
            if (last != 0 && chk == (1<<last)) return 1;
            else return 0;
        }
        //기저조건2 : 방문 체크에 마지막 수가 포함되지 않은 경우
        if ((chk & (1<<last)) != (1<<last)) return 0;
        //기저조건3 : 메모이제이션이 된 경우
        if (dp[ind][chk][last] != INF) return dp[ind][chk][last];

        int result = 0;
        if (last + 1 != 10) {
            result = (result + dfs(ind-1, chk, last + 1)) % MOD;
            result = (result + dfs(ind-1, chk - (1<<last), last + 1)) % MOD;
        }
        if (last - 1 != -1) {
            result = (result + dfs(ind-1, chk, last - 1)) % MOD;
            result = (result + dfs(ind-1, chk - (1<<last), last - 1)) % MOD;
        }
        return dp[ind][chk][last] = result;
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1][1<<10][10];
        for (int a = 0; a < N+1; a++) {
            for (int b = 0; b < (1<<10); b++) {
                for (int c =0; c < 10; c++)
                    dp[a][b][c] = INF;
            }
        }
     }

    public static void solve() throws IOException {
        int result = 0;
        for (int i = 0; i < 10; i++)
        	//0~9 모두 방문한 케이스만 계산함 
            result = (result + dfs(N, (1<<10) - 1, i)) % MOD;
        bw.write(result + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}