Backjoon(백준) 10844번 - 쉬운 계단 수(Java)

1. 풀이 힌트 

 - N의 자릿수 길이의 숫자에서 계단 수 조건으로 0부터 9까지의 숫자가 끝에 올 수 있는 횟수를 카운트한다. 앞의 규칙으로 4자리수 까지 구한뒤 비교해보면 규칙이 보일 것이다.

ex) 한 자리수에서 0부터 9까지 숫자가 끝에 올 수 있는 경우의 수

N = 1 일 때 

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1

2. 풀이 과정

 - 한 자리수 부터 네자리 까지 0 ~ 9의 숫자가 끝에 올수 있는 경우의 수를 나열하면 밑과 같다

0 1 2 3 4 5 6 7 8 9 // 0 ~ 9까지
0 1 1 1 1 1 1 1 1 1 // N = 1
1 2 2 2 2 2 2 2 2 1 // N = 2
2 3 4 4 4 4 4 4 3 2 // N = 3
3 6 7 7 7 7 7 7 6 3 // N = 4

 1) 위와 같은 결과를 점화식으로 도출하면 dp[N][i] = dp[N - 1][i - 1] + do[N - 1][i + 1]이 된다 (i >= 1 and i <= 10)

 2) 코드로 구현할 때는 2차원 배열을 선언하여 각 자리수 N의 0 부터 9까지 끝이 올 수 있는 자릿수를 저장한다.

 *dp[N][i] : N : N크기의 자리 숫자를 나타냄. i: 0부터 9까지 끝에 올 수 있는 자리 수.

 3) 2차원 배열의 크기를 선언할 때 주의할 점

  3-1) 0으로 끝나는 수 카운트

   - 0으로 끝나는 수를 카운트 하기 위해서는 이전 자리 값인 -1의 끝자리가 필요 한데, -1 끝자리는 존재할 수 없는 수이기 때문에 배열의 시작점을 i = 1으로하여 0으로 끝나는 수를 카운트 할때 0의 값을 갖는 i = 0번째 값을 더해 줄 수 있도록 한다. 

  3-2) 9로 끝나는 수 카운트

 - 9로 끝나는 수를 카운트할 때도 마찬가지로, 9다음의 수 10이 없기 때문에 배열의 크기를 최대 12로 선언하여 i = 10이 됐을 때 0의 값을 같는 i = 11값들을 더할 수 있게 설정한다.

3. 코드 구현

  - 각 배열에 값을 넣을 때 MOD를 나누고 sum을 계산 하면서 한번 더 MOD로 나눠주어 계산하는 결과와 sum을 계산할 때 만 MOD를 계산하는 결과는 같지만, int의 범위를 넘지 않기 위해 dp를 계산할 때도 MOD를 나눠준다.

package dp2.backjoon;

import java.util.Scanner;

public class Main {
    
    static final int MOD = 1000000000;

    public static void main(String[] args) {
        
        int[][] dp = new int[101][12];
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= 10; j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD; //1) MOD
            }
        }
        
        int sum = 0;
        for (int i = 1; i <= 10; i++) {
            sum = (sum + dp[n][i]) % MOD; //2) MOD
        }
        
        System.out.println(sum);

    }

}

 문제 링크 ( https://www.acmicpc.net/problem/10844 )

 

* 참고 블로그

( https://sihyungyou.github.io/baekjoon-10844/ )

 

* What is 1E10? 

( https://www.quora.com/What-is-1E10 )

If it is scientific notation, the easiest way to think of it is the ‘E’ stands for ‘times 10 raised to the … power’, so this would be 1 times 10 raised to the 10th power (or 1 followed by 10 zeros)

Thus 1E10 is 10,000,000,000