문제

백준 오르막 수 문제 보러가기



문제점 해결

가장 자신 없는 문제인 DP문제를 연습할 겸 백준에 있는 DP 필수 문제집을 참고해 문제풀이를 하고 있다. 이 문제는 내가 DP문제에 정말 약하구나라고 느꼈던 문제 중 하나이다.

n\k 0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9 10

위의 표는 끝자리 수가 k일때의 경우의 수로 만약 N이 2이고 끝자리 수가 1인 경우의 오르막 수는 01과 11뿐이다.(수는 0으로 시작할 수 있다.)

N이 3이고 K가 7인 경우의 수를 생각해보자. 숫자가 _ _ 7 일때 7앞에 올 수 있는 수는 0~6까지 즉, N이 2이고 K가 7인 경우의 수인것이다. 여기서 세울 수 있는 점화식 dp[n][k] = dp[n-1][0] + dp[n-1][1] + … + dp[n-1][k] 이다.



풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[][] dp = new int[1001][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 answer = 0;
		for (int i : dp[N]) {
			answer += i;
		}
		
		System.out.println(answer%10007);
	}
}