[백준 - 11057번] 오르막 수 - 자바(JAVA) 정리 및 해설

이번에 풀어볼 문제는 DP문제인 오르막 수입니다. 

11057번: 오르막 수

 

이 문제에서 핵심적으로 봐야할 것은 이차원 배열을 통해서 이 문제를 이해하는 방식이라고 생각합니다. 

제가 이 문제에서 사용한 방식은 DP[][] 이렇게 있을때 앞의 [] 배열은 N을 뜻하고 뒤의 배열은 [] N에 따라 붙는 한자리 숫자를 뜻합니다. 

 

글로 표현하기가 어려워서 (혹은, 설명을 잘 못해서) 간단하게 예를 들어서 이야기하면

DP[2][1] => 2 자리의 숫자 길이 중 맨 뒤의 숫자가 1인 경우의 수를 뜻하는 것입니다. 

 

간단하게 위의 사진으로 예를 들면 DP[1][1] 은 1 개자리의 숫자 중 맨뒤의 숫자가 1인 경우 즉, 1일때 경우가 하나 있으며

DP[2][1]은 2자리의 숫자 길이중 맨두의 숫자가 1인 경우 즉, ?1 -> 01, 11 ,21 과 같이 3가지 경우가 존재하게 됩니다.

 

결국 정리하면 DP[N][K]는 N개 자리의 숫자 중 가장 맨뒤의 숫자가 K일때의 경우의 수 라 생각하면 됩니다.

 

이때 가능한 그 앞자리의 수가 0, 1 을 제외한 나머지 수는 불가능합니다.  왜냐하면 2나 9가 들어오면 91 21이 되어서 오르막 수가 되지 못하기 때문입니다.

즉, 이런식으로 [N][k]의 경우를 구해야한 다면, N-1의 K와 같거나 작은 수를 선택해서 모든 경우의 수를 다 더해야합니다

 

이것을 그대로 코드로 변환 한것은 21번째줄로 K보다 같거나 숫자가 작은 모든 경우의 수를 다 더해가는 경우입니다.

그이후에 각 값에 대해서 10007로 나눕니다.  마지막으로는 모든 값을 더한 다음에 10007로 나눕니다. 

 

/** 2020. 4. 30. 오후 11:21:04
 * @author ventulus95
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	
	static int dp[][];

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1][10];
		for(int i =0; i<10; i++){
			dp[1][i] = 1;
		}
		for(int i=2; i<=n; i++){
			for(int j=0; j<10; j++){
				for(int k=0; k<=j; k++){
					dp[i][j] += dp[i-1][k];
					dp[i][j] %= 10007;
				}
			}
		}
		int sum = 0;
		for(int i=0; i<10; i++){
			sum += dp[n][i];
		}
		System.out.println(sum%10007);
	}
}