DP - 11057(오르막 수)

11057번: 오르막 수 (acmicpc.net)

11057번: 오르막 수

 

해당 문제를 풀기전 

DP - 10844(쉬운 계단 수) :: 꿈을 보는 개발자 (tistory.com)

DP - 10844(쉬운 계단 수)

 

위 문제에 대해서 이전 게시물에 포스팅하였습니다. 

 

오르막 수 문제도 이와 비슷한 갈피를 통해서 문제를 풀었습니다. 여기서 쉬운 계단 수와 다른 점은 쉬운 계단 수는 1과 9일 경우에만 조건을 통해서 설정 해주었지만, 이 경우에는 자리에 들어갈 숫자보다 같거나 큰 경우에만 값을 넣을 수 있습니다. 그렇기 때문에 이전 문제를 활용하여서 for을 0~9까지 검사하도록 해주고 현재 자리수의 숫자보다 크거가 값은 경우에는 값을 더해서 갱신 해주도록 하였습니다. 

 

package com.company;

import java.util.Scanner;

public class Main {
    static int number[][] = new int[1001][10];

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

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

        for(int i=2; i<=level; i++){
            for(int j = 0; j<num; j++){
               for(int n=9; n>=j; n--){
                   number[i][j] += (number[i-1][n])%10007;
               }
            }
        }

        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)%10007);
    }
}