[백준] 1562 계단 수 [JAVA]

문제링크 : www.acmicpc.net/problem/1562

1562번: 계단 수

첫 자리 숫자의 경우 1~9까지 오게, 아닐 경우에는

1. 현재숫자가 0이면 다음은 1, 9이면 8

2. 현재 숫자가 0이나 9가 아니면 위 아래 숫자로 다음 숫자를 정했다.

이런 경우를 중복 없이 모두 확인한다.

재귀 탐색 중, 현재 상태가 0~9까지 모두 등장한 계단수인지 판단하기 위해 그 상태를 비트마스크로 확인했다.

(10개가 등장했거나 안했거나(0 or 1)로 가능하기 때문에 10자리 이진수로 표현 가능 => 2^10 크기 배열 선언)

어떤 숫자가 등장했는지와 더불어  (몇 번째 수인지, 이전에 무슨 수를 골랐는지)에 따라 결과 값이 다르다고 판단하여

dp[0~9 등장 여부][idx 번째 수][이전에 고른 숫자] 로 저장하였다.

비트마스크 연산의 경우 인자로 넘겨주며 계산했으면 조금 더 빨랐을 거란 걸 다른 사람 풀이를 보고 알았다.

나의 경우 함수 내에 bitmask 값을 얻기 위해 10번의 연산을 한다.

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static int selected[];
	public static long dp[][][];
	public static long dfs(int idx, int prev) {
		int bitmask = 0;
		int check = 1;
		for(int i=0;i<10;i++) {
			if(selected[i] > 0) {
				bitmask += check;
			}
			check*=2;
		}
		//기저사례
		if(idx==N) {
			if(bitmask == (1<<10)-1) {
				return 1;
			}else {
				return 0;
			}
		}

		if(prev!=-1) {
			if(dp[bitmask][idx][prev]!=-1) {
				return dp[bitmask][idx][prev];
			}
		}
        
		long ret = 0;
		if(idx==0) {
			for(int i=1;i<=9;i++) {
				selected[i] += 1;
				ret += dfs(idx+1,i);
				ret %= 1000000000;
				selected[i] -= 1;
			}
		}else {
			if(prev==9) {
				selected[8] += 1;
				ret+= dfs(idx+1,8);
				selected[8] -= 1;
			}else if(prev == 0) {
				selected[1] += 1;
				ret+= dfs(idx+1,1);
				selected[1] -= 1;
			}else {
				selected[prev+1] += 1;
				ret += dfs(idx+1,prev+1);
				selected[prev+1] -= 1;
				selected[prev-1] += 1;
				ret += dfs(idx+1,prev-1);
				selected[prev-1] -= 1;
			}
		}
		ret %= 1000000000;
		if(prev!=-1) {
			return dp[bitmask][idx][prev] = ret;
		}
		return ret;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		selected = new int[10];
		dp = new long[1<<10][N][10];
		for(int i=0;i<1<<10;i++) {
			for(int j=0;j<N;j++) {
				for(int k=0;k<10;k++) {
					dp[i][j][k] = -1;
				}
			}
		}
		System.out.println(dfs(0,-1));
	}

}