[백준] 11057 오르막 수 자바

 

풀이

 

일단 문제에 제시된 규칙에 따라 오르막 수를 구해보면

 

N = 1 일때 (한자리 수)

0 ~ 9 까지 총 10개의 오르막수가 구해진다.

 

N = 2 일때 (두자리 수) 

00, 01, 02, ...  09 (10가지)

11, 12, 13, ... 19 (9가지)

22, 23, 24, ... 29 (8가지)

...

88, 89 (2가지)

99 (1가지) 

총 55가지 오르막 수가 존재하게 된다.

 

끝자리가 i (0 ~ 9) 로 끝나는 오르막 수의 개수는 n - 1 자리수의 (0 ~ i) 의 합과 같다.

 

예를들어 2자리 숫자의 오르막수 중에서 9로 끝나는 오르막 수의 개수는

1자리 숫자의 오르막 수 중 끝자리가 0 부터 9까지인 수의 개수의 합과 같다.

 

2자리 숫자의 오르막수 중 8로 끝나는 숫자의 개수는

1자리 숫자의 오르막수 중 끝자리가 0 ~ 8 인 오르막수의 개수의 합과 같다.

 

이 문제는 규칙성을 발견하면 이전 값을 바탕으로 어떤 값이든 구할 수 있다는 동적 프로그래밍 원리를 적용한 것으로,

이중 배열을 사용하여 자리수별 경우의 수를 구하는 유형이다.

 

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final long MOD = 10007L;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n + 1][10];
        for (int i = 0; i <= 9; i++) {
            dp[1][i] = 1;

        }

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

        long result = 0;
        for (int i = 0; i <= 9; i++) {
            result += dp[n][i] % MOD;
        }
        System.out.println(result % MOD);
    }
}

 

모듈러 연산에 주의 하자 

위 코드의 시간 복잡도는 100n 이므로 O(n) 으로 표현할 수 있다.