백준 10844 쉬운 계단 수(JAVA)

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

10844번: 쉬운 계단 수

 

 

 

풀이)

import java.util.Scanner;

public class Main_BJ_10844_쉬운계단수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // dp[i][j]: i번째 자리수가 j일 때 계단수 값
        long[][] dp = new long[n+1][10];
        long mod = 1000000000;

        // 첫 번째 자리수는 1개
        for(int i=1; i<10; i++){
            dp[1][i] = 1;
        }

        for(int i=2; i<=n; i++){
            for(int j=0; j<10; j++){
                if(j==9){
                    dp[i][9] = dp[i-1][8]%mod;
                }
                else if(j==0){
                    dp[i][0] = dp[i-1][1]%mod;
                }
                else
                    dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%mod;
            }//j
        }//i

        long ans = 0;
        for(int i=0; i<10; i++){
            ans += dp[n][i];
        }
        System.out.println(ans%mod);
    }//main
}

솔직히 일일히 찾아보다가 어떻게 표현해야할지 몰라서 찾아봤다.

내가 찾은 방식이랑 비슷한 아이디어였는데, 결국 0과 9를 제외하고는 양 옆을 탐색한다는 것이다.

 

따라서 2차원 배열을 선언하고, dp[i][j]라면 i번째 자리수가 j일때 계단수 값을 의미한다.

예를 들어,,,

3XX라면, 34X와 36X를 봐야하므로... dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]이 점화식이 됨을 확인할 수 있다.

 

또한!!

dp는 long으로 잡아야 하고, ans 또한 mod 값으로 나눠줘야 한다는 사실을 잊지 말자!

 

 

참고 블로그

https://code-lab1.tistory.com/108

[백준] 10844번 쉬운 계단 수 (자바 풀이)