11057 : 오르막 수 - JAVA

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

 

DP 문제이다. 쉬운 계단 수(https://www.acmicpc.net/problem/10844)를 이전에 풀어본적이 있었고, 이 문제 풀이 경험에서 답을 찾을 수 있었다. 

 

풀이 방법은 간략하게 이미지와 같다.

이미지는 다른 블로그에서 퍼왔다.

숫자가 한자리일 경우 한자리만 있으므로 오롯이 하나만 설정해두면 된다.

한자리 이상이 있을때는 다음과 같다. 

두자리일 경우 첫째 자리가 0일 경우 00, 01, 02..., 09 10개, 1일 경우 11, 12, 13...., 19 9개, .. 9일경우 99로 1개 총 55개 나온다.

세자리일 경우 첫째자리가 0이면 001, 002,... , 099 55개, 1이면 45개 .. 9면 1개이다.

그러면 이런 규칙을 발견할 수 있다.

n자리일 경우 첫째자리가 0이면 n-1자리의 0~9 의 합, 1이면 n-1자리의 1~9의 합 .. 9면 n-1자리의 9의 합이 된다는 규칙이다.

이를 도식화 하면 다음과 같은 일반항이 나온다.

num[i][j] = num[i][j-1] + num[i-1][j]

 

합을 구해서 답을 도출해낼 수 있다.

제가 많이 부족하기에 혹시나 설명이 부족하면 댓글 남겨주시면 매우 고맙겠습니다.

 

소스코드

import java.util.*;
import java.io.*;
public class Main{
    static final int mod = 10007;
    static int[][] num;
    static int total;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        num = new int[1001][10];
        for(int i = 0; i <10; i++){
            num[1][i] = 1;
        }
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < 10; j++){
                if(j == 0){
                    num[i][0] = 1;
                    continue;
                }
                num[i][j] = (num[i][j-1] + num[i-1][j])%mod;
            }
        }
        for(int i = 0; i < 10; i++){
            total += num[n][i];
        }
        System.out.println(total%mod);
    }
}