[백준]10844: 쉬운 계단 수 - JAVA

[백준]10844: 쉬운 계단 수 

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

풀이

DP문제는 진짜진짜 많이 풀어봐야 할 것 같다. 아직 완전히 이해하고 풀 수준이 안되는 것 같다.

 

이 문제는 dp함수를 2차원 배열로 만들었다. dp배열 의미하는 뜻은 dp[길이][마지막 자리수가 계단이 되는 경우의 수] 이다. 

 

n이 1 일때는 다음과 같다. n이 1일때 0은 결과에 포함되지 않으므로 계산하지 않는다.

dp[1][1]	1	길이가 1일이고 끝자리의 수가 1일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][2]	1	길이가 1일이고 끝자리의 수가 2일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][3]	1	길이가 1일이고 끝자리의 수가 3일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][4]	1	길이가 1일이고 끝자리의 수가 4일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][5]	1	길이가 1일이고 끝자리의 수가 5일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][6]	1	길이가 1일이고 끝자리의 수가 6일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][7]	1	길이가 1일이고 끝자리의 수가 7일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][8]	1	길이가 1일이고 끝자리의 수가 8일때 앞에 올 수 있는 수는 없으므로 1이다.
dp[1][9]	1	길이가 1일이고 끝자리의 수가 9일때 앞에 올 수 있는 수는 없으므로 1이다.

 

n이 2일때는 다음과 같다. 

dp[2][0]	dp[1][1]	길이가 2이고 끝자리의 수가 0일때는 앞에 올 수 있는 수는 1밖에 없으므로 dp[1][1]이다.
dp[2][1]	dp[1][0] + dp[1][2]	길이가 2이고 끝자리의 수가 1일때는 앞에 올 수 있는 수는 0과 1이므로 dp[1][0] + dp[1][2]이다.
dp[2][2]	dp[1][1] + dp[1][3]	길이가 2이고 끝자리의 수가 2일때는 앞에 올 수 있는 수는 1과 3이므로 dp[1][1] + dp[1][3]이다.
dp[2][3]	dp[1][2] + dp[1][4]	길이가 2이고 끝자리의 수가 3일때는 앞에 올 수 있는 수는 2과 4이므로 dp[1][2] + dp[1][4]이다.
dp[2][4]	dp[1][3] + dp[1][5]	길이가 2이고 끝자리의 수가 4일때는 앞에 올 수 있는 수는 3과 5이므로 dp[1][3] + dp[1][5]이다.
dp[2][5]	dp[1][4] + dp[1][6]	길이가 2이고 끝자리의 수가 5일때는 앞에 올 수 있는 수는 4과 6이므로 dp[1][4] + dp[1][6]이다.
dp[2][6]	dp[1][5] + dp[1][7]	길이가 2이고 끝자리의 수가 6일때는 앞에 올 수 있는 수는 5과 7이므로 dp[1][5] + dp[1][7]이다.
dp[2][7]	dp[1][6] + dp[1][8]	길이가 2이고 끝자리의 수가 7일때는 앞에 올 수 있는 수는 6과 8이므로 dp[1][6] + dp[1][8]이다.
dp[2][8]	dp[1][7] + dp[1][9]	길이가 2이고 끝자리의 수가 8일때는 앞에 올 수 있는 수는 7과 9이므로 dp[1][7] + dp[1][9]이다.
dp[2][9]	dp[1][8]	길이가 2이고 끝자리의 수가 9일때는 앞에 올 수 있는 수는 8밖에 없으므로 dp[1][8]이다.

여기서 중요한 부분은 끝자리의 수가 0, 9일때이다. 나머지 수들은 모두 자신의 값 -1, +1한 값들이 앞에 올 수 있지만 0은 -1한 값이, 9는 +1한 값이 앞에 올 수 없으므로 따로 처리해 주어야 한다.

 

그리고 문제의 조건대로 값을 계속 나누어 줘야 하는것도 잊으면 안된다.

 

코드

import java.util.*;
 
public class Main {    
    
    static long mod = 1000000000;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        
        long[][] dp = new long[n + 1][10];
        for(int i = 1; i <= 9; i++) {
            dp[1][i] = 1; //1자리 수의 i번째 수가 계단이 되는 경우는 한가지 밖에 없으므로 초기화.
        }
        
        for(int i = 2; i <= n; i++) {
            for(int j = 0; j < 10; j++) {
                if(j == 0) dp[i][j] = dp[i - 1][j + 1] % mod; //끝 자리가 0일때는 앞에 올 수 있는 수가 1밖에 없다.
                else if(j == 9) dp[i][j] = dp[i - 1][j - 1] % mod; //끝 자리가 9 일때는 앞에 올 수 있는 수가 8밖에 없다.
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }    
        }
        
        long result = 0;
        for(int i = 0; i < 10; i++ ) {
            result += dp[n][i];
        }
        System.out.println(result % mod);
    }    
}