[JAVA] 10844. 쉬운 계단 수

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

문제 접근 과정

• 1자리 수는 모두 계단 수로 정의됩니다.
  • 1자리 수는 1부터 9까지 존재하며, 이는 모두 계단 수의 조건을 만족합니다. 따라서, 길이가 1인 경우 각각의 숫자(1~9)는 계단 수의 개수가 1개씩입니다.
  • 예외적으로, 문제에서 0으로 시작하는 수는 계단 수로 간주하지 않습니다.
• 자릿수가 증가할 때, 숫자가 뒤에 추가된다고 가정합니다.
  • 숫자가 앞에 추가된다고 보는 것보다 뒤에 추가된다고 생각하는 편이 직관적입니다. 예를 들어, 길이가 3인 경우는 길이가 2인 계단 수의 뒤에 숫자를 추가하여 구성할 수 있습니다.
  • 예를 들어, 길이가 2인 계단 수 12에 숫자 3을 추가하면, 길이가 3인 계단 수 123이 됩니다.
• 특수한 경우: 마지막 자리가 0 또는 9인 경우
  • 마지막 자리가 0인 경우: 그 앞의 숫자는 무조건 1이어야 합니다. 따라서 (길이-1, 1)에서만 유효한 계단 수를 가져올 수 있습니다.
  • 마지막 자리가 9인 경우: 그 앞의 숫자는 무조건 8이어야 합니다. 따라서 (길이-1, 8)에서만 유효한 계단 수를 가져올 수 있습니다.
• 일반적인 경우: 마지막 자리가 1~8인 경우
  • 마지막 자리가 1~8이라면, 그 앞의 숫자는 각각 양쪽에 인접한 숫자일 수 있습니다. 예를 들어:
    • 마지막 자리가 3인 경우:
      • 앞의 숫자가 2일 때: (길이-1, 2)의 계단 수를 추가합니다.
      • 앞의 숫자가 4일 때: (길이-1, 4)의 계단 수를 추가합니다.
  • 즉, (길이, 현재 자리 숫자)는 (길이-1, 현재 자리 숫자 - 1)과 (길이-1, 현재 자리 숫자 + 1)의 합으로 계산됩니다.
• 모든 숫자에 대해 계단 수를 계산하여 누적합니다.
  • 길이가 N인 계단 수의 개수는 각 자리(0~9)에 대해 계단 수의 합을 계산한 결과입니다.
  • 모듈러 연산(MOD)을 각각 적용하여 숫자가 너무 커지는 것을 방지합니다.

 

점화식

dp[i][j]: 길이가 i이고, 마지막 자리가 j인 계단 수의 개수입니다.

• 점화식
  • dp[i][0]=dp[i−1][1]
  • dp[i][9]=dp[i−1][8]
  • dp[i][j]=dp[i−1][j−1]+dp[i−1][j+1] (1 ≤ j ≤ 8)
•  초기 조건
  • dp[1][j]=1 (1 ≤ j ≤ 9)
  • 길이가 1인 경우, 각 숫자가 계단 수의 조건을 만족하므로 dp[1][j]는 모두 1입니다.
  • 단, dp[1][0]=0, 즉 0으로 시작하는 계단 수는 존재하지 않습니다.

1.  

코드

import java.io.*;

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

	private static long cal(int length, int lastDigit) {
		if (length == 1) {
			return (lastDigit >= 1 && lastDigit <= 9) ? 1 : 0;
		}

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

		long result = 0;

		if (lastDigit > 0) {
			result += cal(length - 1, lastDigit - 1);
		}

		if (lastDigit < 9) {
			result += cal(length - 1, lastDigit + 1);
		}

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

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

		long total = 0;

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

		System.out.print(total);
	}
}