[DP] 백준 11057 오르막 수 (Ascending Number)

BackJoon 

# 11057 - 오르막 수 (Ascending Number)

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

대표적인 DP문제입니다.

DP[N][L] 을 N자리수의 L이라는 숫자가 올 경우, 오르막 수 조건에 해당하는 경우의 수 라고 하겠습니다. 

DP[3][7] 이라고 하면 _ _ 7 을 뜻합니다. 그렇 다면 2번째 자리는 어떤 숫자가 올 수 있을까요?

오르막 수 규칙에 의하면 0 ~ 7 이라는 숫자가 올 수 있습니다. 즉 N자리 L 숫자가 온다면, N-1자리 숫자는 0 ~ L 범위의 숫자가 올 수 있는 것입니다. 지금은 하나의 경우인 즉 L숫자를 가정했지만, 모든 경우의 수를 고려해야 하기 때문에 시그마로 식을 세워야 합니다. 결국 

DP[N][L] = DP[N-1][0] + DP[N-1][1] + DP[N-1][2] +  . . . .  + DP[N-1][L] 인 것이지요....

그렇다면 이제 초기화를 생각해 봅시다. 한자리 인 경우 0 이 오는 경우는? 1가지.. 그냥 0 오는것이죠. 1이 오는 경우는? 그냥 1 오는 것이지요.. 

따라서 다음과 같이 초기화를 해줘야 합니다. 

for(int i=0; i<10; i++) dp[1][i] = 1;

자 그 다음 1자리 인 경우 모든 경우의 수를 고려했고, 

2자리인 경우일 때 3중 포문을 돌면서 위 점화식을 코드화하면 됩니다.

K는 N-1자리에 올 수 있는 숫자의 범위를 나타냅니다. 

이를 코드로 옮겨보면 다음과 같습니다.

package BackJoon;

import java.util.Scanner;

public class AscendingNumber {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int mod = 10007;
		
		int dp[][] = new int[n+1][10];
			
		//우선 초기화해줘야 함
		//1자리수 인경우 각 숫자가 들어갈 경우의 수 저장
		for(int i=0; i<10; 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-1][k]; //시그마는 += 으로 대체될 수 있음.
					dp[i][j] %= mod;
				}
			}
			
		}
		
		int ans = 0;
		for(int i=0; i<=9; i++){
			ans += dp[n][i];			
		}
		
		System.out.println(ans%=mod);
	}

}