(백준 1562) 단계 수(Java) 정리

가면을 조금사용

(완전한 코드)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static final int MOD = 1000000000;
	public static int goUpStair(int()()() dp, int idx, int N, int cur, int visited) {
		if(dp(idx)(cur)(visited) !
= 0) return dp(idx)(cur)(visited);
		
		if(idx == N) 
			if(visited == ((1 << 10) - 1)) return 1;
			else return 0;
		
		int count = 0;
		
		if(cur < 9) count += goUpStair(dp, idx + 1, N, cur + 1, visited | (1 << (cur + 1)));
		if(cur > 0) count += goUpStair(dp, idx + 1, N, cur - 1, visited | (1 << (cur - 1)));
	
		return dp(idx)(cur)(visited) = count %= MOD;
	}
	
    public static void main(String() args) {
        int N;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = 0;
        try
        {
            N = Integer.parseInt(br.readLine());
            int()()() dp = new int(N + 1)(10)((1 << 10));
            
            for(int i = 1; i < 10; i++) {
            	count += goUpStair(dp, 1, N, i, (1 << i));
            	count %= MOD;
            }
            
            bw.write(Integer.toString(count));
            
            bw.flush();
            bw.close();
            br.close();
        }catch (Exception e)
        {
            e.printStackTrace();
        }
    }
}

int()()() dp = new int(N + 1)(10)((1 << 10));
// dp(남은 수의 길이)(현재 위치)(방문한 숫자)

dp 배열은 현재 위치에서 단계 수를 취할 수 있는 경우에만 1보다 큰 값을 갖습니다.

for(int i = 1; i < 10; i++) {
    count += goUpStair(dp, 1, N, i, (1 << i)); //1부터 9까지의 수로 시작하는 경우를 모두 더함
    count %= MOD;
}

단계 수는 0을 제외한 1에서 9 사이의 숫자로 시작할 수 있습니다.

$N = 10$이면 1XXXXXXXXX에서 9XXXXXXXXX까지의 값이 나올 수 있습니다.

if(dp(idx)(cur)(visited) !
= 0) return dp(idx)(cur)(visited);
//dp의 값이 이미 나왔으면 굳이 다시 계산하지 않고 바로 return

이 코드를 넣지 않으면 계산하는 데 시간이 오래 걸립니다.

if(idx == N) 
    if(visited == ((1 << 10) - 1)) return 1; //모든 수 0~9를 방문했으면 1 return
    else return 0; //아닌 경우 0 return

if(cur < 9) count += goUpStair(dp, idx + 1, N, cur + 1, visited | (1 << (cur + 1)));
if(cur > 0) count += goUpStair(dp, idx + 1, N, cur - 1, visited | (1 << (cur - 1)));
//cur == 9면 다음 수는 8이어야만 한다.


//cur == 0이면 다음 수는 1이어야만 한다.

함수를 실행하고 값을 반환할 때마다 모드를 통해 공유해도 상관없습니다.