백준 10844번 쉬운 계단 수 (java)

[Silver I] 쉬운 계단 수 - 10844

문제 링크

성능 요약

메모리: 14548 KB, 시간: 104 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 12일 17:04:03

문제 설명

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

재귀 바텀 업 방식으로 풀이하였다.

 

간단하게 재귀함수를 어떻게 구성할지 먼저 생각해보자.

 

1~9에 -1 과 +1을 해주며 재귀 함수를 호출하면 된다.

 

하지만 이렇게 전부 방문을 하게 된다면 9 * 2^100 만큼의 연산이 발생하니 절대 시간제한안에 해결할 수 없다.

 

이를 해결하기 위해 dp를 적용할 필요가 있다.

 

dp는 간단하게 적용할 수 있다.

 

같은 자릿수와 같은 숫자를 가지고 있다면 굳이 재귀함수를 호출할 필요가 없다.

 

예를 들어 

 

? ->2  -> ?

   ->2   ->?

 

이런 식으로 두 번째 자리에 2가 존재한다면 해당 자릿수에 존재하는 같은 수에서 나올 수 있는 가짓수는 동일하다. 

 

이를 이용해 dp를 구성하면 간단하게 문제를 해결할 수 있다.

 

전체 코드

public class Main {
    static int N=0;
    static BigInteger dp[][];
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        dp = new BigInteger[10][N+1];

        for(int  i = 0;i<10;i++){
            for(int j = 0;j<N+1;j++){
                dp[i][j] = BigInteger.valueOf(-1);
            }
        }
        BigInteger sum = BigInteger.valueOf(0);
        for (int  i = 1;i<10;i++){
            sum = sum.add(cur(i,1));
            sum = sum.mod(BigInteger.valueOf(1000000000));
        }

        bw.write(sum + "");
        bw.flush();
    }

    static BigInteger cur(int now, int depth){
        if(now < 0 || now > 9){
            return BigInteger.valueOf(0);
        }
        if(!Objects.equals(dp[now][depth], BigInteger.valueOf(-1))){
            return dp[now][depth];
        }
        if(depth == N){
            return BigInteger.valueOf(1);
        }
        return dp[now][depth] = cur(now+1, depth+1).add(cur(now-1, depth+1));
    }
}