[백준-10844번] 쉬운 계단 수 - Java

🚀 문제

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

🚀 접근 방법

DP 문제이다.
 
끝 자리 개수를 저장하는 것이 포인트
 
0은 1, 9는 8만 올 수 있다.
그 사이 값들은 -1, +1이 올 수 있다.
 
끝자리가 2라면 이전 2가 온 개수 만큼 끝자리가 1과 3 자릿수에 더해주면 된다.
 

🚀 코드

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        final long mod = 1000000000;

        int n = Integer.parseInt(br.readLine());

        long[][] dp = new long[n+1][10];

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

        for(int i=2; i<=n; i++){
            for(int j=0; j<=9; j++){
                if(j<9)
                    dp[i][j+1] +=(dp[i-1][j]%mod);
                if(j>0)
                    dp[i][j-1] +=(dp[i-1][j]%mod);
            }
        }

        bw.write(Long.toString((Arrays.stream(dp[n]).sum()%mod)));

        bw.flush();
        br.close();
        bw.close();
    }
}