[백준] 10844번 쉬운 계단 수 _ JAVA ( 주석 설명 )

처음에 자신있게 점화식을 f(N) = f(N-1) - fibo(N) 으로 세웠지만, 틀렸습니다.. ㅎㅎ

 

조건

- N자리 숫자의 계단수 개수를 출력하라.

 

풀이

- N자리 숫자의 각 value(0~9)가 가지는 계단수를 저장하고, => dp[N][value]

   메모제이션 한 값을 활용한다. (개인적으로는 dp 구조를 생각하기 어려웠음)

- 계단수를 만들기 위해서는, value가 0일 때는 1 / 9일 때는 8 / 이 외에는 value-1, value+1 두가지로 뻗칠 수 있다.

 

https://st-lab.tistory.com/134

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

 

---

 

1번

→ Top-down 방식

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


public class Main {
    //N자리 숫자의 각 value(0~9)가 가지는 계단수를 저장하는 공간이다. => N자리 숫자 시작이 각각의 value로 시작
    //100자리 숫자의 계단수 개수를 저장하는 공간이므로, long or Long 자료형으로 생성한다
    static long[][] dp; 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //자릿수의 길이 N을 입력받는다.

        dp = new long[N+1][10]; //N자리 숫자의 각 value(1~9)별로 계단수를 저장할 예정이다.

        //한 자릿수의 각 value(1~9)들의 계단수는 1개이다.
        //0은 실제로 계단수는 아니지만, 재귀로 계산을 할 때 개수를 카운팅하여 세줘야 하므로 1로 설정한다.
        //solve(2,1) : 1 다음에 올 수 있는 경우의 수는?
        //= solve(1,0) + solve(1,2)
        for(int i=0;i<10;++i){
            dp[1][i] = 1L;
        }
        
        long result = 0; //각 value 계단수의 합 또한 int 범위를 넘을 수 있으므로 long으로 정의를 해준다. 
        for(int i=1;i<10;++i){
            result += solve(N, i); //N자리 숫자의 각 value(1~9)별 계단수들을 합한다.
        }
        
        System.out.println(result%1000000000); //N자리 숫자의 계단수를 출력한다.
    }

    //Top-down 방식
    private static long solve(int length, int value) {
        if(dp[length][value]==0) {
            if (value == 0) { //해당 자릿수에 대한 value가 0일 경우 다음 자릿수는 1밖에 못 온다.
                dp[length][value] = solve(length - 1, 1);
            } else if (value == 9) { //해당 자릿수에 대한 value가 9일 경우 다음 자릿수는 8밖에 못 온다.
                dp[length][value] = solve(length - 1, 8);
            } else { //위 경우를 제외하고는 다음 자릿수는 value-1, value+1 모두 올 수 있다.
                dp[length][value] = solve(length - 1, value - 1) + solve(length - 1, value + 1);
            }
        }

        return dp[length][value] % 1000000000; //100자리 숫자의 계단수 개수를 저장하는 공간이므로, long 범위를 넘을 수 있어 나눠준다.
    }
}

 

---

 

2번

→ Bottom-up 방식

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


public class Main {
    //N자리 숫자의 각 value(0~9)가 가지는 계단수를 저장하는 공간이다. => N자리 숫자 시작이 각각의 value로 시작
    //100자리 숫자의 계단수 개수를 저장하는 공간이므로, long or Long 자료형으로 생성한다
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //자릿수의 길이 N을 입력받는다.

        dp = new long[N+1][10]; //N자리 숫자의 각 value(1~9)별로 계단수를 저장할 예정이다.

        //한 자릿수의 각 value(1~9)들의 계단수는 1개이다.
        //0은 실제로 계단수는 아니지만, 재귀로 계산을 할 때 개수를 카운팅하여 세줘야 하므로 1로 설정한다.
        //solve(2,1) : 1 다음에 올 수 있는 경우의 수는?
        //= solve(1,0) + solve(1,2)
        for(int i=0;i<10;++i){
            dp[1][i] = 1L;
        }
        
        long result = 0; //각 value 계단수의 합 또한 int 범위를 넘을 수 있으므로 long으로 정의를 해준다.
        for(int i=1;i<10;++i){
            result += solve2(N, i); //N자리 숫자의 각 value(1~9)별 계단수들을 합한다.
        }

        System.out.println(result%1000000000); //N자리 숫자의 계단수를 출력한다.
    }

    //Bottom-up 방식
    private static long solve2(int length, int value){
        for (int i = 2; i <= length; ++i) {
            for (int j = 0; j < 10; ++j) {
                //Top-down은 재귀이므로 return 과정에서 나머지를 계산하면 됐지만,
                //Bottom-up에서는 그대로 그 값을 저장하기 때문에 저장하기 전에 나머지 계산을 해야한다.
                if (j == 0)
                    dp[i][j] = dp[i - 1][1] % 1000000000; 
                else if (j == 9)
                    dp[i][j] = dp[i - 1][8] % 1000000000;
                else
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % 1000000000;
            }
        }

        return dp[length][value];
    }
}