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

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

오르막 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	13024	6284	4958	47.774%

문제

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

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

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

입력

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

출력

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

---

이전 문제인 쉬운 계단수를 풀고 나면, 이 문제도 간단하게 점화식을 세울 수 있습니다.

다만 주의할 점은, 범위가 1 계단 차이가 아닌, l번째 자연수부터 l+k 인 오르막수 들이 모두 범위에 들어가므로,

d[i][l] += d[i-1][k] 를 하면서 k의 범위를 잘 구하는게 요점이다.

나같은 경우에는,

package test2;
import java.util.*;
public class Test2 {
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            long sum=0;
            long[][] d = new long[1001][11];
 
            for(int x=0; x<=9;x++){
                d[1][x] = 1;
            }
            // 규칙 d[n][k] = d[n-1][k+1] + d[n-1][k];
            for(int i =2; i<=n ; i++){
                for(int l=0 ; l<=9 ; l++){
                    for(int k=l ; k<=9 ; k++){
                        d[i][l] += (d[i-1][k])% 10007;
                    }
                }
            }
            
            for(int x=0; x<10;x++){
                sum = sum + d[n][x];
            }        
            System.out.println(sum% 10007);
        }
}
 

굵게 표시된 부분이 추가가 됬는데, 사실 저 범위를 거꾸로 for(int k=l ; k<=9 ; k++)가 아닌 

for(int k=0 ; k<=l ; k++) 로 해도 가능하다. 그 이유는 어차피 저장 방식은 똑같기 때문,

하지만, 문제의 방향에 맞추려면 k=l; k<=9 가 맞다.

---