[백준] 11057. 오르막 수 (Java)

문제

11057번: 오르막 수

 

 

알고리즘

다이나믹 프로그래밍(DP)

 

 

풀이

[N + 1][10] 크기의 2차원 배열를 선언하여 다음과 같이 저장하였다.

dp[i][j] = 길이 i의  j로 끝나는 숫자 중 오르막 수의 개수

 

만약 j로 끝나는 오르막 수라면 그 전에는 j보다 작거나 같은 수가 올 수 있다.

따라서 점화식은 다음과 같다.

dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j]

 

위 방식으로 길이 N까지 경우의 수를 구한 후 dp[N][0] ~ dp[N][9] 를 더해 출력한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int divisor = 10_007;

		int N = Integer.parseInt(br.readLine());
		int[][] dp = new int[N + 2][10];
		Arrays.fill(dp[1], 1);

		for (int i = 2; i <= N + 1; i++)
			for (int j = 0; j < 10; j++)
				for (int k = 0; k <= j; k++)
					dp[i][j] = (dp[i][j] + dp[i - 1][k]) % divisor;

		System.out.println(dp[N + 1][9]);
	}
}