[백준] 계단 수 1562 - JAVA

문제

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

전략

N = 100 → 완전탐색으로는 불가능

• dp로 고민하자
• 처음에는 dp[i][j]로 i : i자리 수 중 , 마지막이 j로 끝나는 계단수로 설정
• 단순히 dp[i-1][j-1] + dp[i-1][j+1]로 더하면 계단수가 나올것이라는 생각
• 하지만 989898989와 같이 계단수로 이루어져있지만 모든 자리수가 나오지 않는 경우가 있어 각 자리 수의 방문체크가 필요하다는 판단
• dp[i][j][k| 1<<j] = i자리 수 중 , 마지막이 j로 끝나는, j번째 수 방문된 상태를 가지는 수 k 로 비트 마스킹으로 방문처리하는 부분을 추가.
• dp[i-1][j-1][k] + dp[i-1][j+1][k] 로 모든 j-1, j+1을 끝자리로 가지는 모든 방문 여부를 확인한 수들을 다 더해준다
  • ex) 989898989의 경우와 789898989의 경우 모두 확인
• 따라서 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 dp[N][0 부터 9로 끝나는 경우][(1<<10)-1]로 구할 수 있다.
  • 모든 수가 방문되었으면 1111111111 이 요구 되기에 (1<<10)-1로 표현한다.

코드

package acmicpc; 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Back1562_계단_수 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    static int N;
    static final int NUM = 1000000000;
    static int[][][] dp; // 
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        dp = new int[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]) % NUM;
                    }
                    else if(j == 9){
                        dp[i][j][k | (1<<j)] = (dp[i][j][k | (1<<j)] + dp[i-1][j-1][k]) % NUM;
                    }
                    else{
                        dp[i][j][k|(1<<j)] = (dp[i][j][k | (1<<j)] + dp[i-1][j-1][k] + dp[i-1][j+1][k]) % NUM;
                    }
                }

            }
        }
        int result = 0;
        for(int i = 0; i < 10;i++){
            result = (result + dp[N][i][(1<<10)-1]) % NUM;
        }
        System.out.println(result);
    }
}

유의사항

• 0일때와 9일때는 각각 0-1, 9+1의 수가 존재하지 않는다.
• 초기 값으로 1자리수에 1을 설정해야 2자리 수 부터 점화식이 적용가능하다.
• 1<<j와 or k(기존 방문여부) 연산을 통해 방문여부를 갱심한다.