[백준 1057번] 오르막 수- java

문제 설명

1. N이 주어진다.

2. 수가 오름차순이어야 한다(현재 자리수의 전에 지금보다 '큰'숫자가 와서는 안된다.

3. 설명할게 더 없다.

풀이 과정

 1. DP로 문제를 풀었다( bottom-up으로 풀었음)

 2. 이전에 풀었던 쉬운 계단 수 를 보고 생각해보면 거의 비슷한 문제이고, 굉장히 쉽게 풀 수 있을 것이다.

 3. 요점은 이전까지의 모든 숫자에 현재 숫자를 더하면 된다는 것이다.

 4. 예를 들어 3개 자리수의 4라는 숫자가 있으면 앞에서 (3으로 끝나는 2개 자리수 숫자 전체 수) + (2로 끝나는 2개 자리수 숫자 전체 수) ... 이렇게 하면 된다.

 5. 솔직히 더 설명할게 없다...  이제 슬슬 더 어려운 내용들을 풀어야 하는데, 난이도가 높아지니 문제 풀이가 조금 힘들어지는 것다.

코드

import java.util.*;

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

		int N = sc.nextInt();
		int sum[][] = new int[N][10];

		for(int i=0; i<10; i++) {
			sum[0][i] = 1;
		}
		
		for(int i=1; i<N; i++) {
			for(int j=0; j<10; j++) {
				for(int k=0; k<=j; k++) {
					sum[i][j] += sum[i-1][k];
					sum[i][j] %= 10007;
				}
			}
		}
		int ans = 0;
		for(int i=0; i<10; i++) ans += sum[N-1][i];
		ans %= 10007;
		
		System.out.println(ans);
	}
}