DP - 10844(쉬운 계단 수)

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

 

쉬운 계단 수 문제였지만 마냥 쉽지만은 않았습니다. 우선 2차원 배열을 활용하여서 자리수가 낮은 수부터 결과값을 갱신해 나가는 형태를 보였습니다. 2차원 배열을 활용한 이유는 자리수와 자리수에 나오는 숫자에 따라서 결과가 나누어 지기때문에 자리수와 자리수에 나오는 숫자에 따른 결과를 구분해주기 위해서 2차원 배열을 사용했습니다. 

 

이때, 문제가 되는 부분은 숫자 0과 9입니다. 숫자가 0일 경우 다음에 나올 수는 계단수 조건을 충족하기 위해서는 1만 나오고 9일 경우에는 8만 나올수 있습니다. 따라서 값을 갱신 할 때, 이 두개의 숫자가 나올 경우의 조건을 따로 설정해주어야할 필요가 있었습니다. 

 

Bottom - up 방식을 통해서 아래의 코드를 작성하였습니다. 

 

package com.company;

import java.util.Scanner;




public class Main {
    static long number[][] = new long[101][10];

    public static long cal(int level , int num){

        long sum = 0;
        for(int i =1; i<10; i++){
            number[1][i] = 1;
        }

        for(int i=2; i<=level; i++){
            for(int j = 0; j<num; j++){
                if(j == 0){
                    number[i][j] = (number[i-1][1])%1000000000;
                }
                else if(j == 9){
                    number[i][j] = (number[i-1][8])%1000000000;
                }
                else{
                    number[i][j] = (number[i-1][j+1] + number[i-1][j-1])%1000000000;
                }
            }
        }

        for(int k =0; k<10; k++){
            sum += number[level][k];
        }
        return sum;
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n,10)%1000000000);
    }
}

 

이때, 값을 갱신해줄 때마다 문제의 조건처럼 1000000000의 나머지값을 갱신 해주었습니다. 

 

부족했던 점

이전과 같이 Top-down 방식으로 풀어보고 싶었으나 갈피를 잡지 못하였습니다. 계속 생각해도 풀리지 않아서 다른 풀이를 참고하여서 2차원 배열을 사용해야 함을 알았고 이를 통해서 문제를 풀어나갔습니다. 위와 비슷한 경우의 문제도 이를 참고하여서 풀 수 있어야 합니다.