(8) [C++, Java] 백준 No.11057 : 오르막 수

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-9-DP-문제-풀이8-백준-No11057-오르막-수

 

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

int d[1001][10];

int main()
{
    int n;
    cin >> n;

    // d[1][0~9], "길이가 1이고 0~9로 끝나는 수"에 대한 값 초기화
    for (int i = 0; i <= 9; i++)
        d[1][i] = 1;

    // d[n][0] ~ d[n][9]를 점화식을 이용해서 계산
    for (int i = 2; i <= n; i++){
        for(int j = 0; j <= 9 ; j++){
            for (int k = 0; k <= j; k++){
                d[i][j] += d[i-1][k];
                d[i][j] %= 10007;
            }
        }
    }

    // d[n][0] ~ d[n][9] 를 모두 더하여 "길이가 N일 때 오름수의 개수"를 구함
    int sum = 0;  
    for (int i = 0; i <= 9; i++)
    {
        sum += d[n][i];
        sum %= 10007;
    }
    
    cout << sum;
}

# Java

import java.util.*;
import java.math.*;

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