자바(백준) 11057 오르막 수

오답 노트 & 새로 알게 된 점

오르막 수는 규칙성이 쉽게 보였다. 다만 이차원 배열을 사용해야 한다는 것을 늦게 알게 되어, 문제를 푸는데 시간이 좀 걸렸다.

 

dp[i][j]라 할 때, i 길이 수에서 j 숫자로 시작하는 숫자들의 개수를 의미한다.

즉, dp[2][3]은 길이가 2인 숫자들 중, 앞이 3으로 시작하는 오르막 수들의 개수이다.

 

2자리 부분을 봐보자.

0으로 시작하는 곳은 1자리인 0~9가 반복, 1로 시작되는 숫자는 1~9, 2로 시작되는 숫자는 2~9 등등 된다.

3자리 부분에서는 2자리 총합부터 시작하여 점점 하나씩 빼게 된다. 

 

---

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = atoi(br.readLine());
        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 <= 9; j++) {
                for (int k = j; k <= 9; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }
 
        int sum = 0;
 
        for (int i = 0; i < 10; i++) {
            sum += dp[N][i];
        }
 
        System.out.println(sum % 10007);
    }
}