[Baekjoon]11057.오르막수(DP)

Baekjoon 

#11057. 오르막수 

http://www.acmicpc.com/problem/11057

---

DP의 대표적인 문제로 쉬운 계단 수 문제랑 비슷한 방식으로 접근하면 될 것 같았다.

먼저 쉬운 계단수 문제에서 힌트를 얻어 오르막수의 경우의 수를 저장할 배열 d를 다음과 같이 정했다.

d[N][L] : N자리 수 중에서 L로 끝나는 오르막 수 개수

예를 들어 d[3][5]는 3자리수 중에서 일의 자리가 5로 끝나는 오르막수, 즉 ＿ ＿ 5 의 형태를 가진 오르막수의 경우의 수다.

생각을 해보면 5 앞에 두 자리 오르막수 중에서 마지막 자리가 5로 끝나는 오르막수가 오면 세자리가 된 그 수 또한 오르막 수가 된다.

이것을 점화식으로 쓰면

d[3][5] = d[2][0] + d[2][1] + d[2][2] + d[2][3] + d[2][4] + d[2][5]

이를 일반화 하면

d[N][L] = d[N-1][0] + d[N-1][1] + d[N-1][2] + ··· + d[N-1][L] 

위 식이 이번 문제를 푸는 데 핵심이다.

그런데 N=1일때 N-1 자리, 즉 0자리 오르막수에 대한 정의는 할 수 없으므로 1자리 오르막수에 대한 초기화를 해야한다.

한 자리 오르막수는 0, 1, 2, 3, ... ,9 이렇게 10개이므로 각 숫자로 끝나는 오르막수의 경우의 수는 모두 1이다. 

d[1][L] = 1

이후에 N=2 부터 n까지 3중 for문을 이용하여 d[N][L]을 구했다.

문제에서 구하고자 하는것은 N자리 오르막수의 모든 경우의 수이므로

d[N][0] + d[N][1] + d[N][2] + ··· + d[N][9]

이것을 구하면 된다.

문제에서 10007로 나눈 나머지를 출력하라고 했으므로 ans%10007을 출력했다.

그런데 처음에 제출했을때 출력은 되는데 답이 틀렸다고 했는데 그때 배열d를 int 선언했기 때문이었다. 

자리수가 작은 숫자에 대해서는 문제가 없었지만 큰 자리수들을 계산할 때 int범위를 초과하기 때문에 그런것 같았다.(n<=1000이므로)

또한 d[N][L]을 구할 때 각 값을 10007로 나눈 후에 저장해야만 정답으로 처리가 되었다. 계속 틀리길래 다른 사람들이 푼 것을 보고 고쳤다. (이건 이유를 생각해봐야겠다.)

<전체 코드>

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

public class _11057 { 

	static int n;
	static long[][] d;
	static int MOD = 10007;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		d = new long[n + 1][10];

		for (int i = 0; i < 10; i++) {
			d[1][i] = 1; 
		}

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k <= j; k++) {
					d[i][j] += d[i - 1][k];
					d[i][j] %= MOD;
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < 10; i++) {
			ans += d[n][i];
		}
		System.out.println(ans % MOD);
	}

}