백준 JAVA 10844 : 쉬운 계단 수

하나도 안 쉬운 계단 수 문제 

DP 너무너무 어려움 ㅜㅜㅜㅜㅜㅜㅜㅜ 눈물 난다요 

배열들의 규칙을 찾아내는 요령이 아직 부족한 것 같다 많이 풀어봐야 될 듯

 

Dynamic Programming 의 Bottom - Up 방식을 활용하여 문제를 해결하였다.

 

가장 먼저 규칙을 살펴 보아야 한다. 

행 부분은 N, 즉 길이를 의미하고 열 부분은 계단수의 마지막 수를 의미한다. 

첫번째 행을 보면, 길이가 1이기 때문에 가장 앞자리에 올 수 없는 0을 제외하고 1개씩 수가 존재하는 것을 볼 수 있다. 

두번째 행을 보면, 길이가 2이기 때문에 가장 마지막에 모든 숫자가 올 수 있다. 

 

[2][2] 라는 자리의 뜻은, 길이가 2이며 마지막에 2가 오는 수, 즉 12와 32를 뜻한다.

이는 첫번째 행의 [1][1]과 [1][3]값을 더한 것이 된다.  

[2][0]을 살펴보면, 올 수 있는 수는 10 하나 뿐이다. 이는 0의 계단수가 1뿐이기 때문이다. 

[2][9]를 살펴보면, 올 수 있는 수는 89 하나 뿐이다. 이는 9의 계단수가 8뿐이기 때문이다. 

 

이를 정리해 보면, 재귀식을 찾아낼 수 있다. 

열의 값이 1보다 같거나 크고 8보다 같거나 작은 경우엔, DP[a][b] = DP[a-1][j-1]+DP[a-1][j+1]이란 식을 찾아낼 수 있다.

열의 값이 0인 경우엔, DP[a][0] = DP[a-1][1]이 된다.

열의 값이 9인 경우엔, DP[a][9] = DP[a-1][8]이 된다. 

 

따라서, 이러한 코드로 문제를 해결할 수 있었다. 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long result=0;
        long mod = 1000000000;

        long DP[][] = new long[101][10];

        //0번째 행 초기화
        for(int i=0;i<=9;i++)
            DP[0][i]=0;

        //1번째 행 초기화
        DP[1][0]=0;
        for(int i=1;i<=9;i++)
            DP[1][i]=1;

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

        for(int i=0;i<=9;i++){
            result+=DP[N][i];
        }

        System.out.println(result%mod);

    }
}

** 계산의 결과값이 정확하게 나올 수 있도록 모든 계산값을 mod값으로 나누어 주어야 한다.