[백준] 자바 Java, 10844번: 동적계획법 > 쉬운 계단 수

10844번: 쉬운 계단 수

---

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.

0으로 시작하는 수는 계단수가 아니다.

 

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

나의 풀이

• Bottom-up 방식 사용

참고 1)

[백준,BOJ 10844] 쉬운 계단 (JAVA 구현)

package level15_dynamicProgramming;

import java.util.Scanner;

// 백준 10844번 문제] 쉬운 계단 수
public class Baekjoon10844 {

    public static void main(String[] args) {
        //입력start
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        //입력end

        long[][] dp = new long[n+1][10]; //[자릿수][0~9]

        //dp배열 초기화 : 자릿수가 1일 경우 각 숫자가 사용될 수 있는 경우의 수는 1씩뿐!
        for(int i=1; i<=9; i++) {
            dp[1][i] = 1;
        }

        //자릿수가 2인 경우부터 이전 자릿수인 1의 자릿수와 비교하며 다음에 올 수 있는 경우의 수를 구함
        for(int i=2; i<=n; i++) {
            for(int j=0; j<10; j++) { // 0 ~ 9
                if(j == 0) dp[i][j] = (dp[i-1][j+1]) % 1000000000; // 끝자리가 0일 경우는 1일 때만 고려
                else if(j == 9) dp[i][j] = dp[i-1][j-1] % 1000000000; // 끝자리가 9일 경우는 8일 때만 고려
                else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] % 1000000000; // 나머지는 -1, +1 모두 고려
            }
        }

        long sum = 0;
        for(int i=0; i<10; i++) {
            sum += dp[n][i];
        }

        System.out.println(sum % 1000000000);
    }

}​

 

결과

for문 안에서 % 1000000000 을 해주지 않을 경우 오버플로우가 발생함!

for(int i=2; i<=n; i++) {
    for(int j=0; j<10; j++) { // 0 ~ 9
        if(j == 0) dp[i][j] = (dp[i-1][j+1]) % 1000000000; // 끝자리가 0일 경우는 1일 때만 고려
        else if(j == 9) dp[i][j] = dp[i-1][j-1] % 1000000000; // 끝자리가 9일 경우는 8일 때만 고려
        else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] % 1000000000; // 나머지는 -1, +1 모두 고려
    }
}

이 점 주의해야 함!