(7) [C++, Java] 백준 No.10844 : 쉬운 계단 수

문제

풀이

자세한 풀이 : 
https://ldgeao99.tistory.com/entry/챕터3-8-DP-문제-풀이6-백준-No10844-쉬운-계단-수?category=864321

 

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

int d[101][10];

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

    // n이 1일 때 결과가 9이므로 해주는 초기화
    for (int i = 1; i <= 9; i++)
        d[1][i] = 1;

    // d 계산하기
    for (int i = 2; i <= n; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            if (j == 0)
                d[i][j] = d[i-1][j+1];

            else if (j == 9)
                d[i][j] = d[i-1][j-1];

            else
                d[i][j] = d[i-1][j-1] + d[i-1][j+1];

            d[i][j] %= 1000000000;
        }            
    }

    // 구해진 d 합하여 출력하기
    long long sum = 0;

    for(int i = 0; i <= 9; i++)
        sum += d[n][i];
        
    cout << sum % 1000000000 << endl;
}

# Java

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

public class Main {
    public static long mod = 1000000000L;
    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=1; i<=9; i++) {
            d[1][i] = 1;
        }
        for (int i=2; i<=n; i++) {
            for (int j=0; j<=9; j++) {
                d[i][j] = 0;
                if (j-1 >= 0) {
                    d[i][j] += d[i-1][j-1];
                }
                if (j+1 <= 9) {
                    d[i][j] += d[i-1][j+1];
                }
                d[i][j] %= mod;
            }
        }
        long ans = 0;
        for (int i=0; i<=9; i++) {
            ans += d[n][i];
        }
        ans %= mod;
        System.out.println(ans);
    }
}