[알고리즘-JAVA] 백준 알고리즘 10844번 - 쉬운 계단 수

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

길이 N이 주어졌을 때, 인접한 모든 자리의 수의 차이가 1인 계단수를 만드는 방법의 수 구하기

2. 나의 방식대로 문제를 재정의 하자.

d를 정의하기가 까다로웠는데,

힌트를 얻어서 2차원 배열로 정의했다.

d[n][k] => 길이가 n이고, k로 끝나는 계단수 (n=1일때, 1<=k<=9, 이외에는 0<=k<=9)

그래서 d[n][k]의 총 합을 구하면 된다!

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

재귀를 이용하거나(Top-Down) 배열을 통한 반복문 이용.

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader / InputStreamReader사용.

 

2) 시간 복잡도 계산

10 * O(N) => d[n][k]배열을 채우는 복잡도. 

 

5. 주의할 점은 무엇인가?

0과 9, 0은 1밖에 선택할 수 없고, 9는 8밖에 선택할 수 없다는점.

 

6. 풀이 과정

마찬가지로 d[][]배열을 채워나가면서 문제를 해결하면 되는데

길이가 n이고 끝자리가 k인 계단수의 개수를 d[n][k]라고 하면,

길이가 n-1이고 끝자리가 k-1 혹은 k+1인 녀석들의 합만큼 가질 수 있으므로

d[n][k] = d[n-1][k-1] + d[n-1][k+1]이다.

단! 여기서 주의할점은

d[n][0]이나

d[n][9]같은 경우에는

d[n][0] = d[n-1][1] (k>=0)

d[n][9] = d[n-1][8] (k<=9)인 것에 주의해야 한다.

 

Bottom-UP

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

public class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long d[][] = new long[n+1][10];
        long mod = 1000000000;
        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);
    }
}

Top-Down

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

public class Main{
    public static long d[][];
    static long mod = 1000000000;
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        d = new long[n+1][10];
        long sum = 0;
        for (int i = 1; i <=9; i++){
            sum += Calculate(n,i);
        }
        System.out.println(sum%mod);
    }

    public static long Calculate(int n, int k){
        long ans = 0;
        if (n == 1){
            //1~9까지의 경우.
            return 1;
        }

        if (d[n][k] > 0){
            return d[n][k];
        }
        
        if (k == 0){
            d[n][k] = Calculate(n-1,1);
        }
        else if (k == 9){
            d[n][k] = Calculate(n-1,8);
        }
        else{
            d[n][k] = Calculate(n-1,k-1)+Calculate(n-1,k+1);
        }
        
        return d[n][k]%mod;
    }
}