[Baekjoon] 11057_오르막 수

문제(출처: https://www.acmicpc.net/problem/11057)

---

< 오르막 수 >

 

문제 풀이 

 

dp를 사용하여 자릿수가 늘어날수록 현재 값보다 작거나 같을 때의 경우의 수를 더한다. 

 

my solution (Java)

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

public class _11057_ { // 오르막 수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		int dp[][] = new int[n + 1][10];
		for (int i = 0; i < 10; i++) {
			dp[1][i] = 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]) % 10007;
				}
			}
		}

		int result = 0;
		for (int i = 0; i < 10; i++) {
			result = (result + dp[n][i]) % 10007;
		}

		System.out.println(result);
	}
}

변수)
n : 입력값 
dp : 1~N인 오르막 수
result : 길이가 N인 오르막 수 

 

n을 입력받는다. 1 자릿수일 때는 각 경우의 수가 1개이므로 dp[1][0~9]를 1로 초기화한다. 다음 자릿수부터는 현재 값보다 작거나 같은 값을 더해야 한다. 

 

최종 dp[n][0~9] 값을 더해 출력한다. 

---

---