[백준 11057] 오르막 수 (Java)

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

11057번: 오르막 수

접근 방법

전형적인 DP문제라고 하는데 역시나 아직 많이 부족함을 느낀다.

 

2차원배열을 사용한다.

dp[N][0~9]로 수의 길이가 N번일 때, 마지막 자리수가 0 ~ 9 경우의 개수를 각각 담는다.

 

우선 dp[1][0~9]는 모두 1로 따로 설정을 해둔다.

for문을 이용해 2부터 N까지 돌려 값을 구한다.

 

dp[2]의 경우를 예로 들어보자

dp[2][0]은 마지막 자리의 수가 0인 경우 오르막 수 갯수를 구한다.

이 경우에는 00 하나만 존재한다.

 

dp[2][1]은 마지막 자리 수가 1인 경우 오르막 수 갯수를 구한다.

이 경우에는 01, 11이 존재한다.

 

dp[2][2]은 마지막 자리 수가 2인 경우 오르막 수 갯수를 구한다.

이 경우에는 02, 12, 22가 존재한다.

 

dp[2][i]에는 0i ~ ii가 존재한다.

마지막 자리 수가 없다 생각하고 수의 변화를 살펴보면

0일 때 0

1일 때 0과 1

2일 때 0, 1, 2

3일 때 0, 1, 2, 3

...

 

이를 일반화 시키면 다음과 같은 점화식이 나온다.

dp[n][i] = dp[n -1][0] + ... + dp[n-1][i]

 

3중 for문을 구해 배열의 각 값을 구하고

dp[n][0] ~ dp[n][9]의 값을 더한 것에 10007을 나눠 나온 나머지를 출력하면 된다.

 

 

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[][] dp = new int[N + 1][10];


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

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k <= j; k++) {
                    dp[i][j] += dp[i - 1][k];
                    dp[i][j] %= 10007;
                }
            }
        }

        int result = 0;

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

        System.out.println(result % 10007);
    }
}