[BaekJoon] 11057 오르막 수

1.  문제 링크

https://www.acmicpc.net/problem/11057

2.  문제

요약

• 수의 자리가 오름차순을 이루거나 인접한 수가 같은 수를 오르막 수라고 합니다.
• 예를 들어, 2234, 3678, 11119 등이 오르막 수입니다.
• 수의 길이 N이 주어졌을 때, 0으로 시작할 수 있는 오르막 수의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 N이 주어집니다.
• 출력: 첫 번째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력합니다.

3.  소스코드

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

public class Main {
	public int getAscendingNum(int num) {
		if(num == 1)
			return 10;
		else if(num == 2)
			return 55;
		int[][] dp = new int[num + 1][10];
		Arrays.fill(dp[1], 1);
		for(int i = 0; i < 10; i++) {
			dp[2][i] = i + 1;
		}
		for(int i = 3; i <= num; i++) {
			for(int j = 0; j < 10; j++) {
				for(int l = 0; l <= j; l++) {
					dp[i][j] += (dp[i - 1][l] % 10007);
				}
			}
		}
		long ascending_num = 0;
		for(int i = 0; i < dp[num].length; i++) {
			ascending_num += dp[num][i];
		}
		return (int)(ascending_num % 10007);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getAscendingNum(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.

• 길이가 1인 수부터 N인 수까지 각 길이에서의 오르막 수의 개수를 구하는데, 각 길이에서 가장 뒷자리 수가 0인 수부터 9인 수까지의 오르막 수의 개수를 각각 구합니다.

• 길이가 1일 때는 뒷자리 수가 0인 수부터 9인 수까지 모두 오르막 수의 개수가 1이기 때문에 1로 초기화를 시킵니다.

• 길이가 2인 수에서 뒷자리 수가 0인 수부터 9인 수까지의 길이는 아래와 같습니다.

  0	1	2	3	4	5	6	7	8	9
  1	2	3	4	5	6	7	8	9	10

• 길이가 3인 수에서 뒷자리 수가 0인 수부터 9인 수까지의 길이는 아래와 같습니다.

  0	1	2	3	4	5	6	7	8	9
  1	1 + 2	1 + 2 + 3	1 + 2 + 3+ 4	1 + 2 + 3+ 4 + 5	1 + 2 + 3 + 4 + 5 + 6	1 + 2 + 3 + 4 + 5 + 6 + 7	1 + 2 + 3 + 4 + 5 + 6 + 7 + 8	1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9	1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

• 위 개수들을 확인해보면 길이가 3인 수에서 뒷자리 수가 N인 수의 오르막 수의 개수는 길이가 2인 수에서 뒷자리 수가 0인 수부터 N인 수까지의 오르막 수의 개수의 합과 같다는 것을 알 수 있습니다.

• 예를 들어, 길이가 3인 수에서 뒷자리 수가 3인 수를 보면

  • 003
  • 013, 113
  • 023, 123, 223
  • 033, 133, 233, 333

• 이러한 수들이 있는데, 뒷자리 수 3을 제외하고 앞의 두 자리 숫자만 생각해본다면, 위에서부터 길이가 2인 수에서 뒷자리가 0인 수, 1인 수, 2인 수, 3인 수와 같습니다.

• 그렇기 때문에 길이가 N인 수 중 뒷자리가 i인 수의 오르막 수의 개수를 dp[N][i]라고 한다면

  • dp[N][i] = dp[N - 1][0] + dp[N - 1][1] + ... + dp[N - 1][i]

• 이러한 점화식을 세울 수 있습니다.

• 위 점화식을 바탕으로 오르막 수의 개수를 구합니다.

1. 만약 주어진 N이 1이라면, 길이가 1인 오르막 수의 개수는 10개이기 때문에 이를 출력하고 N이 2라면, 길이가 2인 오르막 수의 개수는 55이므로 이를 출력합니다.
2. 길이가 N인 수 중 뒷자리가 i인 수에서의 오르막 수의 개수를 나타내는 2차원 배열 dp를 생성하고 길이가 1인 경우와 길이가 2인 경우에 해당하는 부분들을 초기화시킵니다.
3. 길이가 3인 경우부터 길이가 N인 경우까지 반복문을 돌면서 오르막 수의 개수를 구합니다.
   1. 뒷자리가 0인 수부터 9인 수까지 반복문을 돌며 각 수에서의 오르막 수의 개수를 구합니다.
      • 위에서 세운 점화식을 바탕으로 오르막 수의 개수를 구하는데, 문제에서 오르막 수를 10,007로 나눈 나머지를 출력하라고 하였으므로 뒷자리가 0인 수부터 i인 수까지 더할 때, 해당 수에서의 오르막 수의 개수를 10,007로 나눈 나머지를 더해나갑니다.
4. 3번의 반복문이 종료되었을 때의 dp 배열에서 길이가 N인 수 중 뒷자리 수가 0인 수부터 9인 수까지의 오르막 수의 개수의 합을 구한 후 10,007로 나눈 나머지를 출력합니다.