[백준_11057번] 오르막 수

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

11057번: 오르막 수

[문제]

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

 

[입력 조건]

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_11057 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[][] dp=new int[n+1][10];
		
		for(int i=0;i<10;i++)
			dp[0][i]=1;
		
		/*
		 * dp[n][j]에는 n자리 수이면서 첫째 자리가 j로 시작하는 수를 말한다.
		 * 즉, 0~9까지의 각 숫자(j)를 시작으로 만들 수 있는 수를 모두 더한 값이
		 * n 자리로 만들 수 있는 오르막의 수가 된다.  
		 */
		for(int i=1;i<=n;i++) {
			for(int j=0;j<10;j++) {
				for(int k=j;k<10;k++) {
					dp[i][j]+=dp[i-1][k];
					dp[i][j]%=10007;
				}
			}
		}
		System.out.println(dp[n][0]%10007);
	}

}

 

[고찰] 

 동적 계획법 문제는 어떤 규칙성을 갖고있는지 파악하는 것이 중요하다. dp[i][j]의 의미는 i자리 수 이면서 j로 시작하는 오르막 수의 개수를 말한다. dp를 표로 그려보면 아래와 같다. 

 

i/j	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	10	9	8	7	6	5	4	3	2	1
3	55	45	36	28	21	15	10	6	3	1

 

 2자리로 만들 수 있는 오르막의 수를 예로 들어보면 

 

00, 01, 02, ... ,08, 09 -> 10개

11, 12, 13, ... ,18, 19 -> 9개

...

88, 89 -> 2가지

99 -> 1가지로 총 10+9+...+2+1 = 55가지의 경우의 수가 나온다.

 

즉, i 자릿수를 갖는 오르막수의 개수는 0~9까지의 각 숫자(j)를 시작으로 만들 수 있는 수를 모두 더한 값이 된다.