BOJ) 쉬운 계단 수

쉬운 계단 수

10844번: 쉬운 계단 수

풀이

 

문제 제목은 쉬운 계단 수 인데, 어렵다.. ㅋㅋㅋㅋ

DP 문제를 푼지 오래된 것 같아서 DP 문제를 선택해봤다.

우선 2차원 배열을 사이즈에 따라 생성하는 것 까지는 해놓고 생각을 했다.

n자리 수 때, 0~9 숫자가 몇 번 쓰이는지 저장을 해야 풀 수 있는 문제인가 생각을 해보았다.

한 20분정도 생각했는데 이 방법은 아니었다. 다른 저장 방법은 없을까 고민했지만 떠오르지 않았다.

위의 생각에 빠져서 해당 숫자에서 -1 , +1 사이에 있어야 하는 것을 간과한 것이다..

 

그래서 질문하기 게시판을 참고했다.

코드가 있는 질문들은 과감하게 넘기고 점화식을 물어보는 문제를 봤다.

답변에 나와 같이 2차원 배열을 생성하고, n회차에서 0~9의 숫자가 마지막에 오는 경우를 저장하는 것이었다.

 

어차피 0을 제외한 1~9 숫자는 숫자의 가장 큰 자릿수에 자리할 수 있기 때문에, 이 경우를 따지는 일이 필요가 없었다.

자릿수가 커질수록 마지막 값이 한정적이기 때문에, 마지막 숫자만 확인하면 되는 것이었다.

(dp로 하는 이유는 n=4일 경우 앞에 n=3일 때, n=2일 때, 들어오지 못하는 숫자가 이미 가지치기가 되기 때문에)

 

위의 조건에 따라서 1자리 수일 때 0~9까지 들어가는 경우를 저장해주었다. (1~9 => 1)

그리고, 2~주어진 n 까지 돌면서, dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1] 이라는 식으로 저장했다.

 

i라는 숫자는 앞자리 수의 -1 혹은 +1이 돼야 계단식 숫자가 만들어지기 때문이다.

out of index를 방지하기 위해서, i-1 >=0, i+1 <=9 의 범위 안에서 dp를 저장하면서 MOD로 나눠주었다.

 

그리고 마지막 dp[n]을 저장하고 나서, 자릿수 n에 해당하는 모든 경우의 수를 저장하면서 MOD로 나눴다.

 

 

 

코드

 

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

public class Main {
    final static int NUMSIZE = 10;

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

        br.close();
    }

    private static void solution(int n) {
        int[][] dp = new int[n+1][NUMSIZE];
        final int MOD = 1000000000;

        for(int i=1; i<NUMSIZE; i++) {
            dp[1][i] = 1;
        }
        for(int i=2; i<=n; i++) {
            for (int j = 0; j < NUMSIZE; j++) {
                if(j-1 >=0) {
                    dp[i][j] = (dp[i][j]+dp[i-1][j-1])%MOD;
                }
                if(j+1 <NUMSIZE) {
                    dp[i][j] = (dp[i][j]+dp[i-1][j+1])%MOD;
                }
            }
        }

        int num = 0;

        for(int i=0; i<NUMSIZE; i++) {
            num = (num+dp[n][i])%MOD;
        }
        System.out.println(num);
    }
}