11057.오르막수

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

## 입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

## 출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	51093	25041	19405	47.786%

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

풀이

알고리즘 흐름

자리수	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	10	9	8	7	6	5	4	3	2	1
3	55	45	...	...	...

표를 보면 세로는 자리수 N이고, 가로는 0~9까지의 숫자이다.
채워진값은 dp[n][i] n: 자리수 , i:제일 뒷자리 숫자 를 통해 i를 가지고 N자리수를 만들었을때의 갯수이다.

n=1일때 0,1,2,3,4,5,6,7,8,9 가 가능하고,

n=2일때
i=0 이면 00 01 02 03 04 05 06 07 ...
i=1 이면 11 12 13 ...
순으로 구할수있고
마지막인 9로는 99를 만들수있다.

즉 규칙을 찾아보면, N자리수의 i 번값은 n-1 자리수의 i ~ 9까지의 값을 모두 더한값이다.

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

코드

package 기초1.Day20.정해영;  

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

public class 오르막수 {  

    static int MOD = 10007;  

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

        //이전자리만 고려하면 된다.  

        int n = sc.nextInt();  //자리  

        int[][] dp = new int[n + 1][10];//n:자리수 10:마지막수  

        Arrays.fill(dp[1], 1);  

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

        System.out.println(Arrays.stream(dp[n]).sum()%MOD);  
        sc.close();  
    }  
}

DP와 3중 for문을 사용하는 경우는 처음이여서 구현이 힘들었다. 쉬운문제이고 분명 접근까지 했는데 3중 for문을 사용해도 되는지 생각이 많아졌었다. 그리고

System.out.println(Arrays.stream(dp[n]).sum()%MOD); 

이렇게 마지막에 MOD 연산을 안해서 2번정도 더 에러가 발생했다. 위쪽에서만 해주는게 아니라 실제 나오는값에서도 MOD를 해주자.