[백준] 10844번 쉬운 계단 수 (자바 풀이)

문제

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

10844번: 쉬운 계단 수

풀이

이 문제는 다이나믹 프로그래밍을 이용해서 해결할 수 있다. 

Top-down 방식 혹은 Bottom-up 방식을 사용할 수 있는데, 나는 Bottom-up 방식을 사용하였다.

 

dp 배열을 2차원 배열로 만들어서 사용하면 되는데, 그 의미는 다음과 같다.

예를 들어 dp[3][5]는 3번째 자릿수가 5일때 계단 수이다. 이걸 어떻게 구할 수 있을까?

N=3일때 dp[3][5]는 dp[2][4] + dp[2][6] 이다. 즉, 두 번째 자릿수가 4이거나 6일때의 계단수를 더하면 된다.

이 때 주의해야 할 숫자가 2개 있다. 바로 0과 9이다.

만약 dp[i][0] 을 구해야한다면, dp[i][0] = dp[i-1][1]만 가능하다. 0옆에는 1만 올 수 있기 때문이다.

만약 dp[i][9]를 구해야한다면, dp[i][9] = dp[i-1][8]만 가능하다. 9옆에는 8만 올 수 있기 때문이다.

 

코드를 보고 이해해보자.

 

import java.util.*;
import java.io.*;
 
public class Baekjoon_10844 {
    static int N;
    static long mod = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        long dp[][] = new long[N+1][10];
        
        /* 첫번째 자릿수는 경우의 수가 하나 뿐임 */
        for(int i=1; i<10; i++) {
            dp[1][i] = 1;
        }
        
        
        /* 두번째 자릿수부터 N번째 자릿수까지 탐색 */
        for(int i=2; i<=N; i++) {
            /* 현재 자릿값을 0부터 9까지 탐색*/
            for(int j=0; j<10; j++) {
                // 자릿값이 9라면 이전 자릿값은 8만 가능
                if(j == 9) {    
                    dp[i][9] = dp[i-1][8]%mod;
                }
                // 자릿값이 0이라면 이전 자릿값은 1만 가능
                else if(j==0) {    
                    dp[i][0] = dp[i-1][1] % mod;
                }
                // 그 외는 현재 자릿값의 -1, +1 가능
                else {    
                    dp[i][j] = (dp[i-1][j-1]+ dp[i-1][j+1])%mod;
                }
            }
        }
        
        long ans = 0;
        for(int i=0; i<10; i++) {
            ans += dp[N][i];
        }
        
        System.out.println(ans%mod);
    }
 
}

결과