[Java] 11057. 오르막 수

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

문제 접근 과정

오르막 수의 개수를 계산할 때, 오름차순으로 계산하는 것이 아닌, 맨 끝자리 숫자를 고정했을 때의 관점에서 접근하는 것이 핵심입니다.

• 끝자리 고정 관점
  • 오르막 수는 끝자리 숫자가 0부터 9 중 하나로 고정될 때, 앞의 숫자들이 어떤 값을 가질 수 있는지 계산하는 문제로 바꿀 수 있습니다.
  • 예를 들어, 길이가 2이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:
    • 01, 11 (끝자리 1로 고정)
  • 길이가 3이고 끝자리 숫자가 1이라면 가능한 오르막 수는 다음과 같습니다:
    • 001, 011, 111 
• 현재 자릿수에서 가능한 경우의 수
  • 현재 자릿수의 끝자리 숫자가 j로 고정된 경우, 이 숫자는 이전 자릿수에서 끝자리 숫자가 0부터 j까지인 모든 경우의 수를 합한 것과 같습니다.
  • 예를 들어, 길이가 3이고 끝자리 숫자가 1인 경우:
    • 길이가 2이고 끝자리 숫자가 0 또는 1인 경우의 수를 모두 더한 것과 같습니다.

 

점화식

길이가 n이고 끝자리 숫자가 j인 오르막 수의 개수를 dp[n][j]라고 정의

• 점화식:
  • dp[n][j] = dp[n-1][0] + dp[n-1][1] + ... + dp[n-1][j]
  • 현재 자릿수의 끝자리 숫자가 j라면, 이전 자릿수의 끝자리 숫자가 0부터 j까지 가능한 모든 경우의 수를 합산합니다.
  • 이를 누적합 방식으로 최적화하면 dp[n][j] = dp[n][j-1] + dp[n-1][j]로도 나타낼 수 있습니다.
• 초기 조건:
  • 길이가 1일 때, 끝자리 숫자가 j인 오르막 수는 각 숫자 하나씩만 존재합니다
  •  

    dp[1][j] = 1 (j = 0, 1, ..., 9)

 

 

코드

• dp[n][j] = dp[n-1][0] + dp[n-1][1] + ... + dp[n-1][j]을 이용하여 간단히 구현하였습니다.

import java.io.*;
import java.util.Arrays;

public class Main {
	private static long[][] dp;
	private static final long MOD = 10007;

	private static long cal(int length, int lastDigit) {
		if (length == 1) {
			return 1;
		}

		if (dp[length][lastDigit] != -1) {
			return dp[length][lastDigit];
		}

		long result = 0;

		for (int digit = lastDigit; digit <= 9; digit++) {
			result = (result + cal(length - 1, digit)) % MOD;
		}

		dp[length][lastDigit] = result % MOD;

		return result;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int length = Integer.parseInt(br.readLine());

		dp = new long[length + 1][10];

		for (long[] row : dp) {
			Arrays.fill(row, -1);
		}

		long total = 0;

		for (int i = 0; i <= 9; i++) {
			total = (total + cal(length, i)) % MOD;
		}

		System.out.print(total);
	}
}