[BOJ][11057] 오르막 수

1. 문제 링크

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

2. 사용 알고리즘

DP

3. 풀이

d[n][a] : 길이가 n인 오르막 수의 개수, n번째 자리수는 a

• a == 0일 때, n - 1 자리에 가능한 수 : 0

  • d[n][0] = d[n - 1][0]

• a == 1일 때, n - 1 자리에 가능한 수 : 0, 1

  • d[n][1] = d[n - 1][0] + d[n - 1][1]

• …

• a == 9일 때, n - 1 자리에 가능한 수 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

  • d[n][1] = d[n - 1][0] + d[n - 1][1] + … + d[n - 1][9]

∴ d[n] = d[n - 1][0] + d[n - 1][1] + … + d[n - 1][9]

4. 소스 코드

4-1. C++

4-1-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/11057.cpp

#include <iostream>

using namespace std;

int d[1003][13];

int solve(int n, int a) {
    if (n == 1) return 1;
    if (d[n][a] > 0) return d[n][a];
    for (int i = 0; i <= a; ++i) {
        d[n][a] += solve(n - 1, i);
        d[n][a] %= 10007;
    }
    return d[n][a];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    int ans = 0;
    for (int i = 0; i < 10; ++i) {
        ans += solve(n, i);
        ans %= 10007;
    }
    cout << ans << "\n";
    return 0;
}

4-1-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/11057_2.cpp

#include <iostream>

using namespace std;

int d[1003][13];

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    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] %= 10007;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; ++i) {
        ans += d[n][i];
        ans %= 10007;
    }
    cout << ans << "\n";
    return 0;
}

4-2. JAVA

4-2-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/11057.java

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

public class Main {

    static int d[][] = new int[1003][13];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int ans = 0;
        for (int i = 0; i < 10; ++i) {
            ans += solve(n, i);
            ans %= 10007;
        }
        System.out.println(ans);
    }

    public static int solve(int n, int a) {
        if (n == 1) return 1;
        if (d[n][a] > 0) return d[n][a];
        for (int i = 0; i <= a; ++i) {
            d[n][a] += solve(n - 1, i);
            d[n][a] %= 10007;
        }
        return d[n][a];
    }
}

4-2-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/11057_2.java

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

public class Main {

    static int d[][] = new int[1003][13];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        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] %= 10007;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 10; ++i) {
            ans += d[n][i];
            ans %= 10007;
        }
        System.out.println(ans);
    }
}