[백준,BOJ 11057] 오르막 수( JAVA 구현)

-내 생각

  이 문제의 경우 쉬운 계단 수 문제와 아주 유사하다고 생각했다. 문제를 푸는 과정에서도 유사한 것을 알고 해당 해답을 생각해봤는데, 떠오르지가 않아서 어쩔 수 없이 다시 규칙을 찾아보았다. n이 1일 경우 0~9까지의 10개, n이 2일 경우 0~9까지에 n이 1일 경우에서 1씩 감소하는 형태를 띤다는 것은 쉽게 찾아냈다. 그러나 이를 어떻게 dp배열에 표현해야 할지 감이 잡히지 않아서 결국 다른 분들의 블로그를 참고했다.

 

-해법

  위와 같은 방식은 맞으나 각 자릿수에서 해당 숫자들을 수의 첫 번째 자리가 아닌, 마지막 자리로 생각하면서 dp 배열을 dp[n][10]으로 구현하여 각 자릿수마다 끝자리의 숫자의 경우 앞에 올 수 있는 숫자의 경우의 수를 저장하면 된다. 

예를 들어 아래의 표는 n이 2까지일 경우를 나타낸 것이다. N이 1일 경우는 각 숫자들이 한 개씩 밖에 올 수 없으므로 모두 1로 초기화 된다. N이 2일 경우는 끝자리가 1일 때, 앞자리에 올 수 있는 수는 1~9가 되고, 2일 경우는 2~9... 식으로 한 개씩 감소한다는 것을 알 수 있다. 즉 표에서는 열이 끝자리 기준이므로 앞자리는 열의 값보다 작은 값들의 경우의 수가 들어가면 된다. 1일 경우는 0과 1일 경우의 수, 2일 경우는 0과 1, 2의 경우의 수 말이다.

 

	0	1	2	3	4	5	6	7	8	9
N =1	1	1	1	1	1	1	1	1	1	1
N =2	1	2	3	4	5	6	7	8	9	10

  즉 이 표를 통해 알 수 있는 점화식은 dp[n][j] = dp [n-1][0] + dp [n-1][1] + dp [n-1][2]... + dp [n-1][j]가 된다. 이렇게 만들어진 표에서 n번 째 행의 경우의 수를 모두 더해준 후 나눠주면 된다. 

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[][] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		
		dp = new int [n+1][10]; 
		
        // 초기값은 n이 1일 경우 모두 1로 초기화 한다.
		dp[1][0] = dp[1][1] =dp[1][2] = dp[1][3] =dp[1][4] = dp[1][5] =dp[1][6] = dp[1][7] =dp[1][8] = dp[1][9] =1;
		
		for(int i=2;i<=n;i++) { //  2부터 n까지 반복
			for(int j=0;j<10;j++) { // 0 ~ 9를 탐색하는데,
				for(int k=0;k<=j;k++) { // j를 기준으로 0부터 j까지 탐색
					dp[i][j] += dp[i-1][k]; // k로 탐색한 값을 j에 누적 
				}
				dp[i][j] %= 10007; // 데이터 타입 범위를 위해 나머지 연산 후 저장한다.
			}
			
		}
		
		int sum = 0;
		for(int i=0;i<10;i++) { // n번 째 행의 경우들을 모두 더한다.
			sum+=dp[n][i]; // 더하는 과정에서 값이 또 커질 수 있으므로
		}
		
		System.out.println(sum % 10007); // 더한 값 역시 나머지 연산을 수행한다.
		
		
		
		
	}
	
}