[알고리즘][DP][10844] 쉬운 단계 수

[알고리즘][DP][10844] 쉬운 단계 수

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

[풀이]

• n = 계단의 길이 
• k = 마지막 계단에 들어가는 숫자 ( 0 <=k <= 9 )
• arr[n][k] = 길이가 n인 계단의 수
• arr[n][k] = arr[n-1][k-1] + arr[n-1][k+1] 라는 점화식을 구할 수 있다.
1. 이 때, arr[n][0] = arr[n-1][1], arr[n][9] = arr[n-1][8] 만 가능하기 때문에 for문을 세울 때 고려해줘야 한다.
2. k-1 >= 0 일 때, arr[n][k] = arr[n-1][k-1] 이 가능
3. k+1 <=9 일 때, arr[n][k] = arr[n-1][k+1] 이 가능
• arr[1][k] = 1  (1 <= k <= 9)로 방법의 수를 지정해준다.
• result 변수에 arr[n][k]의 갯수를 세서 넣어준다.
• 정답을 1,000,000,000 으로 나눈 나머지를 출력 -> result%=1,000,000,000
• 주의해야 할 점은 long변수 안에 들어갈 수 있는 범위여야 하기 때문에 2중 for문에서 값을 구하고 한 번 나머지 처리를 해줘야 한다.  

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class q_11052 {
    public static long mod = 1000000000L;
    
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        System.out.println(calc(n));
    }
 
    public static long calc(int n) {
        
        /*
         * n=숫자 자릿수
         * i=끝자리에 들어가는 수
         * Arr[n][i] = n번째 자릿수에 들어가는 숫자
         */
        long[][] arr = new long[n+1][10]; 
        //1. 방법의 수를 구하기 위해 초기 Arr[1][i]=1 로 설정
        //(첫번째부터 0은 들어갈 수 없으니 주의)
        for(int i=1;i<=9;i++) {
            arr[1][i]=1;
        }
        
        
        for(int i=2;i<=n;i++) {
            for(int j=0;j<=9;j++) {
                //배열 초기화
                arr[i][j]=0;
                //j=0 or j=9 일때 방법의 수는 1이므로 이를 처리해줘야한다.
                if( j-1 >= 0) {
                    arr[i][j] += arr[i-1][j-1];
                }
                if( j+1 <= 9) {
                    arr[i][j] += arr[i-1][j+1];
                }
                arr[i][j] %= mod;
            }
        }
        long result=0;
        //result에 답 넣어주기
        for(int i=0;i<=9;i++) {
            result += arr[n][i];
        }
        result %= mod;
        return result;
    }
}