[JAVA] 백준 11057번 【오르막 수】

---

패턴을 찾기 위해 경우의 수를 살펴보자.

 

0으로 시작하는 것도 허용하고, 00 이나 11 과 같이 같은 숫자가 연속된 경우에도 오름차순으로 간주하므로

 

위와 같은 경우의 수가 있을 수 있다.

 

이렇게 색을 칠하면 패턴이 보일 것이다.

 

즉 N자리 i로 시작하는 오르막 수는 N-1자리 i로 시작하는 오르막수부터 N-1자리 9로 시작하는 오르막수를 더하면 된다.

 

Dp[i][j] = Dp[i-1][j] + ····· Dp[i-1][9] 

 

 

위 식을 표현하면 되는데, 나는 for문을 3개 사용하여 표현하였다.

 

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]%mod;
				}
			}
		}

 

i가 2일때를 살펴보면,

 

j=0일 때,

k는 0부터 9까지 진행한다.

즉, Dp[2][0] = Dp[1][0]+ Dp[1][1] +····· + Dp[1][9] 가 된다.

 

j=1 일 때,

k는 1부터 9까지 진행하므로,

즉, Dp[2][1] = Dp[1][1] + ····· + Dp[1][9] 가 된다.

---

결과는 아래와 같다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int [][] Dp = new int[N+1][10];
		int mod = 10007;
		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=j;k<=9;k++) {
					Dp[i][j]+=Dp[i-1][k]%mod; // 오르막 수 경우의 수 구하는 식
				}
			}
		}
		
		int sum=0;
		for(int i=0;i<=9;i++) {
			sum+=Dp[N][i]; 
			sum%=mod;
		}
		System.out.println(sum);
	}
}