[백준] [10844] 쉬운 계단 수 (JAVA) (dp)

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

10844번: 쉬운 계단 수

---

 

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

1 초

256 MB

135802

43522

31606

30.358%

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

---

※ JAVA 코드 (쉬운 계단 수)

import java.io.*;
import java.util.*;

public class Main {
    public static int N;
    public static long[][] dp;
    public static final int MOD = 1000000000;

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

        dp  = new long[N + 1][11];

        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j <= 9; j++){
                if(j == 0) dp[i][j] = dp[i - 1][j + 1] % MOD;
                else if(j == 9) dp[i][j] = dp[i - 1][j - 1] % MOD;
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
            }
        }

        for(int i = 0; i <= 9; i++){
            result += dp[N][i] % MOD;
        }

        System.out.println(result % MOD);
    }
}

---

※ 생각정리 (쉬운 계단 수)

1. 처음 시도에서 틀린 이유 2가지 

1) 수의 뒷자리가 0이거나 9일때 계단수가 2개가 아닌 1개씩 만들어질 수 있으며 수가 커질 수록 그 개수가 많아진다. 또한, 패턴이 존재하지 않는다.

2) 합할때 int정수범위를 초과하는 수가 나와 계산이 정확하게 하려면 long형의 변수를 만들고 최종적으로 한번 더 문제에서 주어진 수로 나누어주어야한다.

 

문제해결을 위해 수의 길이와 맨 마지막수를 확인해야한다. 맨 길이는 1 ~ N까지 올 수 있기 때문에 해당 숫자를 dp[i][j]배열의 i에 담아둔다.

맨 뒷수는 그 이전 수를 확인하여 알 수 있다.

이때, 3가지 경우의 수가 존재한다.

 

1) j가 0인 경우

dp[i][0] = dp[i - 1][1]

2) j가 9인 경우

dp[i][9] = dp[i - 1][8]

3) 둘다 아닌경우

dp[2][1] = dp[1][2] + dp[1][0]

 

다음 길이가 2인 수들을 보면 쉽게 이해가 될 것 이다.

 

12

21, 23

32, 34

43, 45

54,56

65, 67

76, 78

87, 89

98

 

- 새벽코딩 -