[Java] BOJ 11057번 오르막 수

11057번: 오르막 수

---

풀이

 

	0	1	2	3	4	5	6	7	8	9	합
1 자리	1	1	1	1	1	1	1	1	1	1	10
2 자리	10	9	8	7	6	5	4	3	2	1	55
3 자리	55	45	36	28	21	15	10	6	3	1	220

DP를 사용하여 위의 표처럼 계산을 진행하여 해결했습니다.

2자리일 때의 2로 시작하는 오르막 수는 2보다 크거나 같은 수들로 이뤄질 수 있으므로 2자리 바로 이전의 미리 구해둔 1자리일 때의 2 이상의 오르막 수 개수를 전부 더하면 됩니다.

---

코드

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

public class Main {
	public final static int mod = 10007;
	public static int N, answer;
	public static int[][] memo = new int[1001][10];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i <= 9; ++i) {
			memo[1][i] = 1;
		}
		
		for (int i = 2; i <= N; ++i) {
			for (int j = 0; j <= 9; ++j) {
				for (int k = j; k <= 9; ++k) {
					memo[i][j] += (memo[i - 1][k] % mod);
				}
			}
		}
		
		for (int i = 0; i <= 9; ++i) {
			answer += (memo[N][i] % mod);
		}
		
		System.out.println(answer % mod);
	}
}

---

pyo7410/Algorithm