[BOJ] 백준 11057번 - 오르막 수

문제

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

11057번: 오르막 수

 

풀이

DP테이블을 길이가 i일 때 마지막 수가 j인 오르막 수 개수를 가진 이차원 배열로 선언해두면
dp[i][j] 는 앞서 구해진 길이가 i일 때 마지막 수가 j-1인 오르막 수 개수 + 이전 차례의 길이가 i-1일 때 마지막 수가 j인 오르막 수 개수의 합이된다.

• [i][0] : 다음 차례(i)에서 마지막 수가 0인 오르막 수가 될 수 있는 건 기존(i-1)에 마지막 수가 0이었던 수 밖에 없다. (ex: 00)
• [i][1] : 다음 차례에서 마지막 수가 1인 오르막 수가 될 수 있는 건 기존에 마지막 수가 0, 1이었던 수들이다. (ex : 01, 11)
• [i][2] : 다음 차례에서 마지막 수가 2인 오르막 수가 될 수 있는 건 기존에 마지막 수가 0, 1, 2였던 수들 이다. (ex : 02, 12, 22)
• [i][9] : 다음 차례에서 마지막 수가 9인 오르막 수가 될 수 있는 건 기존에 마지막 수가 0, 1, 2, 3, 4, 5, 6, 7, 8, 9였던 수들이다.

 

코드

import java.util.Arrays;
import java.util.Scanner;

// 오르막 수
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // dp[N][L] = 수의 길이가 N일 때, 마지막 수가 L인 오르막 수 개수
        long[][] dp = new long[1001][10];

        // dp[1] 배열 초기화 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        // DP BottomUp
        for (int i = 2; i <= n; i++) {
            dp[i][0] = 1;       // 마지막 수가 0인 오름수가 될 수 있는 건 0000.. 하나밖에 없음
            for (int j = 1; j < 10; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 10007;
            }
        }

        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += dp[n][i];
        }
        
        System.out.println(sum % 10007);
    }
}