백준 10844[자바] java 쉬운 계단 수

문제 링크:https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

▶문제

45656이란 수를 보자.

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

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

---

▶입력

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

---

▶출력

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

---

▶해설

조건을 살펴보겠습니다. 

1. 인접한 모든 자리의 차이가 1인 수들

2. 1,000,000,000 으로 나누기

 

신경써야할 조건은 1번 뿐입니다. 한 자리 수 -> 두 자리 수 -> 세 자리 수로 자리수를 늘려가며 조건을 만족하는 수를 찾으면 됩니다. 끝자리 수가 2~8의 경우 다음 끝자리 숫자에서 +-1이 가능합니다. 하지만 끝자리가 0과9의 경우 0 = 1, 9 = 8 만 가능합니다. 따라서 자리수를 늘려가며, 끝자리에 따라서 더하는 수를 다르게 하면 간단하게 풀립니다.  

따라서 아래의 점화식을 도출할 수 있습니다.

if(num==0){  // index는 자리수, num = 끝의 자리 숫자
    dp[index][num] = solve(index-1, 1);
}
else if(num==9){
    dp[index][num] = solve(index-1, 8);
}
else{
    dp[index][num] = solve(index-1,num+1)+solve(index-1, num-1);
}

전체 코드

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

public class Main {

    static long [][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1][10];

        for(int i=0; i<=9; i++){
            dp[1][i]=1l;
        }
        long result=0;

        for(int i=1; i<=9; i++){
            result+=solve(n, i);
        }

        System.out.println((result)%1000000000);
    }

    private static long solve(int index, int num){
        if(index==1){
            return dp[index][num];
        }

        if(dp[index][num]==0){
            if(num==0){
                dp[index][num] = solve(index-1, 1);
            }
            else if(num==9){
                dp[index][num] = solve(index-1, 8);
            }
            else{
                dp[index][num] = solve(index-1,num+1)+solve(index-1, num-1);
            }
        }

        return dp[index][num]%1000000000;
    }
}