문제

BOJ 10844, 쉬운 계단수

핵심

• 입력의 크기가 $100$이라 구현에 초점을 맞춘다.
• 자릿수가 주어지면 계단수의 개수를 구해야 한다. 개단수란 456656처럼 모든 자리의 차이가 1인 숫자를 말한다. 0으로 시작하는 수는 계단수가 아니다.
• 계단수를 찾기 위해 먼저 규칙을 찾고 점화식을 세워야 한다.
  • 1자리 계단수
    • 1 ~ 9가 올 수 있으므로 9개가 있다.
      • 1, 2, 3, 4, 5, 6, 7, 8, 9
  • 2자리 계단수
    • 앞서 1 ~ 9에 1차이 나는 수를 붙이면 된다.
      • 10, 12, 21, 23, 32, 34, ... 87, 89, 98
• 규칙이 보이는가? 규칙을 좀 더 잘 보이게 자릿수에 맞는 개수를 확인해보자.

{0, 1, 1, 1, 1, 1, 1, 1, 1, 1}; -> 9
{1, 1, 2, 2, 2, 2, 2, 2, 2, 1}; -> 17
{1, 3, 3, 4, 4, 4, 4, 4, 3, 2}; -> 32
{3, 4, 7, 7, 8, 8, 8, 7, 6, 3}; -> 61

• 0의 개수는 이전 1의 개수에 영향을 받고, 1의 개수는 이전 0과 1의 개수에 영향을 받고, 2의 갯수는 이전 1과 3의 개수에 영향을 받고 ... 9는 8의 개수에 영향을 받는다.
• 다음과 같은 점화식을 세울 수 있다.

// dp[i][k] : 자릿수 i일 때 k로 끝나는 계단수의 개수. k는 0 ~ 9.
dp[i][0] = dp[i - 1][1];
dp[i][9] = dp[i - 1][8];
for (int j = 1; j <= 8; ++j)
	dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % 1'000'000'000;

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

long long dp[104][14];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= 9; ++i) 
		dp[1][i] = 1;
	for (int i = 2; i <= n; ++i) {
		dp[i][0] = dp[i - 1][1];
		dp[i][9] = dp[i - 1][8];
		for (int j = 1; j <= 8; ++j)
			dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % 1'000'000'000;
	}
	long long ans = 0;
	for (int j = 0; j < 10; ++j)
		ans += dp[n][j];
	cout << ans % 1'000'000'000;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] dp = new long[n + 4][14];
        for (int i = 0; i < 9; i++)
            dp[1][i] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i][0] = dp[i - 1][1];
            dp[i][9] = dp[i - 1][8];
            for (int j = 1; j <= 8; ++j)
                dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % 1_000_000_000;
        }
        long ans = 0;
        for (int j = 0; j < 10; ++j)
            ans += dp[n][j];
        System.out.println(ans % 1_000_000_000);
        sc.close();
    }
}