[BOJ]10844번: 쉬운 계단 수(java, c++)

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

10844번: 쉬운 계단 수

 

 

방법 1: Top-down

import java.io.*;
 
public class Main {
 
    public static int[][] numbers;
    public static long mod = 1000000000;
    public static int num;
 
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            num = Integer.parseInt(br.readLine());
            numbers = new int[num + 1][10];
 
            System.out.println(calculate(num));
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static long calculate(int i) {
 
        long result = 0;
        
        if (i == 1) {
            for (int j = 1; j <= 9; j++) {
                numbers[i][j] = 1;
                result += numbers[i][j];
            }
            return result;
        }
 
        calculate(i - 1);
 
        for (int j = 1; j <= 9; j++) {
            
            if (j <= 8) {
                numbers[i][j] += numbers[i - 1][j + 1];
            }
        
            if (j == 1) {
                numbers[i][j] += numbers[i - 1][9];
            } else {
                numbers[i][j] += numbers[i - 1][j - 1];
            }
 
            numbers[i][j] %= mod;
        }
 
        if (i == num) {
            for (int j = 1; j <= 9; j++) {
                result += numbers[i][j] % mod;
            }
        }
 
        return result % mod;
    }
}

 

방법 2: Bottom-up

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            int mod = 1000000000;
            
            int[][] numbers = new int[num + 1][10];
 
            for (int i = 1; i <= 9; i++) {
                numbers[1][i] = 1;
            }
 
            for (int i = 2; i <= num; i++) {
                for (int j = 0; j <= 9; j++) {
 
                    if (j == 0) {
                        numbers[i][j] = numbers[i - 1][j + 1];
                    } else if (j == 9) {
                        numbers[i][j] = numbers[i - 1][j - 1];
                    } else {
                        numbers[i][j] = (numbers[i - 1][j - 1] + numbers[i - 1][j + 1]) % mod ;
                    }
                }
            }
            
            long result = 0;
 
            for (int i = 0; i <= 9; i++) {
                result = (result + numbers[num][i]) % mod;
            }
            
            System.out.println(result);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

 

c++소스

#include <iostream>
 
using namespace std;
 
const int DIV = 1000000000;
const int MAX = 100;
int sum[MAX + 1][10];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    // 점화식 : D[N][i] = D[N - 1][i - 1] + D[N - 1][i + 1]
    for (int i = 1; i < 10; i++)
    {
        sum[1][i] = 1;
    }
 
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            if (j < 9)
            {
                sum[i][j] += sum[i - 1][j + 1];
            }
            if (j > 0)
            {
                sum[i][j] += sum[i - 1][j - 1];
            }
            sum[i][j] %= DIV;
        }
    }
 
    // sum[n][i]을 더하는 과정에서 오버플로가 발생할 수 있기 때문에
    // long long 자료형으로 선언
    long long answer = 0;
    for (int i = 0; i < 10; i++)
    {
        answer += sum[n][i];
    }
    cout << answer % DIV;
 
    return 0;
}

 

탑다운과 바텀업의 속도차이가 없었다

 

 

TIP1

인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

 

 

먼저 작은 수들을 가지고 표현해보자. 

길이가 3인 계단수의 맨 끝자리가 4가 되려면,

뒤에서 두번째 자리의 수가 3 또는 5가 되어야 한다.

즉, 길이가 2인 계단수의 맨 끝자리가 3 또는 5 이어야 한다. 

 

다시 표현하면

길이가 3인 계단수의 끝자리가 4인 경우의 수

= 길이가 2인 계단수의 끝자리가 3인 경우의 수 

+ 길이가 2인 계단수의 끝자리가 5인 경우의 수 

 

 

이제 일반적인 점화식을 써보자.

길이가 N인 계단수의 끝자리가 k인 경우의 수를 D[N][k]  라고 하면, 

 

D[N][k] = D[N - 1][k - 1] + D[N - 1][k + 1]

 

 

 

TIP2

예외는 대부분 경계에서 발생한다!

끝자리가 0일때, 9일때의 경우를 처리해주자

 

 

TIP3

마지막 합산하면서 오버플로가 발생할 수 있기 때문에, 

answer는 큰 자료형으로 선언해주자

ex) java : long, c++ : long long 등