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

문제 URL

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

나의 풀이

import java.util.Scanner;

public class Main {
    static int mod = 10007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[1001][10];

        for (int i = 0; i <= 9; i++)
            arr[1][i] = 1;

        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0];
            for (int j = 1; j <= 9; j++) {
                arr[i][j] = (arr[i][j - 1] + arr[i - 1][j]) % mod;
            }
        }

        int sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += arr[n][i];
            sum %= mod;
        }
        System.out.println(sum);
    }
}

느낀점

점화식

arr[i][j] : 길이가ㅏ i이며 마지막 숫자가 j로 끝나는 오르막 수의 총 개수

1. 0<=k<=j arr[i][j] += arr[i-1][k]
2. arr[1][j] = 1;

실수

for (int i = 0; i <= 9; i++) {
    sum += arr[n][i] % mod;
}

이 부분에서 실수를 했다. mod를 나머지 계산한후 sum에 더하니깐 실패할수밖에없다. 더해진 sum에 mod를 나머지계산 하자

for (int i = 0; i <= 9; i++) {
    sum += arr[n][i];
    sum %= mod;
}