백준 10844 쉬운 계단 수 [JAVA]

문제 해석

• 문제에서 입력받는 값은 계단의 길이인 N이다.
• 입력받은 계단의 길이가 N인 계단의 수가 몇개인지 구하면 되는 문제이다.
• 단, 각각의 계단 층은 1이 차이나야 하므로 몇가지 조건이 있다.
  1. 0 다음은 1밖에 오지 못한다는 점 (-1은 존재하지 않는다.)
  2. 9 다음은 8밖에 오지 못한다는 점 (10은 존재하지 않는다.)
     -> 즉 계단에 들어갈 수 있는 값은 0~9뿐이다.
  3. 각 계단의 수를 구할 때마다 1,000,000,000으로 나눈 값의 나머지, 마지막에 출력할 때에도 1,000,000,000으로 나눈 값의 나머지로 구한다.

코드

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

public class Main {
    static Long[][] floor;
    static int N;
    final static long MOD = 1000000000; //나누는 값

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); //계단의 길이
        floor = new Long[N+1][10]; //자리수 1부터 시작

        br.close();

        for(int i = 0; i < 10; i++){ //첫번째 자리수는 1로 초기화
            floor[1][i] = 1L;
        }

        long count = 0; //계단 개수 (누적)

        for(int i = 1; i < 10; i++){
            count += solution(N, i);
        }

        System.out.println(count%MOD);

    }

    // 파라미터 자릿 수 : position, 자리 값 : value
    public static long solution(int position, int value){
        //자릿수의 끝인 1에 도착하면 더이상 탐색 X
        if(position == 1){
            return floor[position][value];
        }

        if(floor[position][value] == null){
            //0 다음음 1밖에 못온다.
            if(value == 0){
                //자릿수 현재 위치 - 1, 자리 값 1
                floor[position][value] = solution(position-1, 1);
            }

            //9다음은 8밖에 못옴
            else if(value == 9){
                floor[position][value] = solution(position-1, 8);
            }

            //1~8이면 value에서 +1, -1한 경우의 수와 같다.
            else{
                floor[position][value] = solution(position-1, value-1) + solution(position-1, value+1);
            }
        }

        return floor[position][value] % MOD; //값을 구할때마다 MOD로 나눠주기
    }

}

결과

느낀 점

• 문제 해석만 꽤 오래 걸렸던 문제이다. 처음에 이 문제를 읽었을 때 이게 무슨 말이지? 계속 읽어도 읽어도 이해가 안되어서 애를 좀 먹었지만 그래도 다른 사이트의 이 문제 해석을 읽어보니 이해할수 있었다.
• 근데 DP는 좀 더 공부해야할 것 같다. 아직 혼자서 완전히 이해하고 풀 수 있는 수준이 되지 못해서... 아직 멀었다😥