백준 10844 쉬운 계단 수 (자바) - DP

쉬운 계단 수 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

81205

24853

17802

28.637%

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

 

---

이 문제는 잘 안 풀려서 풀이들을 검색해보고 참고했다.

찾아본 결과 dp배열을 일차원이 아닌 2차원으로 만들어 풀어야 했다.

dp[n][m] 에서 n은 숫자의 길이이고, m은 마지막 숫자를 의미한다.

 

예를 들어 길이가 2인 숫자들 중 계단 수를 구하라고 하면 마지막 자리에는 0부터 9가 올 수 있는데,

마지막 자리에 0이 왔을 경우(dp[2][0] 경우) 그 앞자리에는 1만 올 수 있다.

마지막 자리에 9가 왔을 경우에는 그 앞자리에 8만 올 수 있다.

그리고 마지막 자리에 1 ~ 8 이 올 경우에는 x-1, x+1 두 가지 숫자가 올 수 있다.

 

길이가 3인 숫자들 중 계단 수를 구할 때는

dp[3][0] 의 경우 두 번째 자리에는 1만 올 수 있고, 두번째 자리가 1인 경우는 위에서 구한 dp[2][1]의 값과 같다.

dp[3][1~8]의 경우 두 번째 자리에는 x-1, x+1 두 가지 숫자가 올 수 있고, 따라서 dp[2][x-1] + dp[2][x+1] 값과 같다.

dp[3][9]의 경우 두 번째 자리에는 8만 올 수 있고, 두 번째 자리가 8인 경우는 dp[2][8]과 같다.

 

따라서 점화식을 써보면 dp[n][0] = dp[n-1][1]이고

dp[n][1~8] = dp[n-1][x-1]+dp[n-1][x+1]이고, dp[n][9] = dp[n-1][8]이다.

dp[n]의 [0]~[9]까지의 값을 모두 더하면 정답이 된다.

 

*주의할 점 : 이 문제에서 1,000,000,000으로 나눈 나머지 값을 구하라고 했는데 이는 정답이 엄청나게 큰 숫자가 나온다는 것이고, 따라서 계산 결과들을 저장할 dp배열을 int 배열이 아닌 더 큰 long 배열로 만들어줘야 한다.

---

import java.util.Scanner;

public class Main {
    static long[][] dp;
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        dp = new long[n+1][10];
        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }
        count(n);
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += dp[n][i];
        }
        System.out.print(sum % 1000000000);
    }
    static void count(int n) {
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i-1][1] % 1000000000;
            for (int j = 1; j < 9; j++) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
            }
            dp[i][9] = dp[i-1][8] % 1000000000;
        }
    }
}