[Algorithm] DP - 백준10844

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 10844번의 계단 오르기 문제를 해결한 과정을 정리하고자 합니다.

 

해당 문제는 N자리 숫자의 계단 수를 구하는 문제입니다.

 

1. 문제 해결 과정

1) n == 1일 때,

- 한자리 숫자의 경우 1 ~ 9까지 총 9개가 계단수입니다.

 

2) n == 2 일 때,

- 두 자리 숫자의 경우,  총 17개입니다.

12, 23, 34, 45, 56, 67, 78, 89 (8개)

10, 21, 32, 43, 54, 65, 76, 87, 98 (9개)

 

3) n == 3일 때,

- 세 자리 숫자의 경우, 총 32개입니다.

123, 234, 345, 456, 567, 678, 789 (7개)

987, 876, 765, 654, 543, 432, 321, 210 (8개)

101, 212, 323, 434, 545, 656. 767, 878, 989 (9개)

121, 232, 343, 454, 565, 676, 787, 898 (8개)

 

이 문제에서는 n번째 자리에 위치한 숫자는

(n - 1) 번째 자리 숫자보다 1 작은 수가 나올 수 있는 경우의 수  + (n -1) 번째 자리 숫자보다 1 큰 수가 나올 수 있는 경우의 수로

DP를 구현할 수 있습니다.

이를 그림으로 확인하면 다음과 같습니다.

따라서, 이를 알고리즘화 하면 아래의 코드로 구현할 수 있습니다. 

stair[i][j] = stair[i - 1][j - 1] + stair[i - 1][j + 1]

 

2. 주의할 점 

하지만, 주의할 점은 0보다 작은 자연수는 없으므로 자리 숫자에 0이 있으면 경우의 수는 (위치한 자릿수 - 1)의 1 큰 수의 경우만 고려해야 합니다.

stair[i][0] = stair[i - 1][1]

또한, 9는 9보다 1이 큰 한자리 숫자는 없으므로, (위치한 자리수 - 1)의 1 작은 수의 경우만 고려해야 합니다.

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

 

마지막으로, 해당 알고리즘 결과를 제출하는데 여러 번 오답이 발생했습니다.

그 이유는, 최종 결과를 도출하는 과정에서 중간에 이미 long의 범위를 벗어나서 올바른 값을 도출하지 못했기 때문입니다.

(자바 long의 범위는 -2^63 ~ 2^63 -1)입니다.

 

해결책은 모듈러 연산을 적용하는 것입니다.

 

모든 경우의 수는 마지막 자릿수의 1부터 ~ 9까지의 경우를 더하면 완성이 됩니다. 이후, 10억으로 나눠도 되지만,

연산 가능 범위를 벗어날 수 있으므로, 모듈러 연산을 적용하여 각 배열에 저장할 때마다 MOD로 나머지 연산을 해주고 

최종적으로 마지막 숫자들을 더한 후, 다시 MOD로 나머지 연산을 해주면 동일한 결과를 얻을 수 있습니다.

        long result = 0L;
        for (int i = 0; i < 10; i++) {
            result += stair[N][i];
        }

(A + B) % p = ((A % p) + (B % p)) % p

 

3. 최종 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main10844 {

    static final long MOD = 1000000000;
    static int N;
    static long[][] stair;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        stair = new long[N + 1][10]; // (n 자리수), (0 ~ 9)

        long result = doStairDp();
        System.out.print(result % MOD);
    }

    static long doStairDp() {

        for (int i = 1; i<10; i++) {
            stair[1][i] = 1; // 첫번째 자리수가 i 일때는 모두 1
        }

        for (int i = 2; i <= N; i++) {

            for (int j = 0; j < 10; j++) {

                if (j == 0) {
                    stair[i][0] = stair[i - 1][1] % MOD;
                }

                else if (j == 9) {
                    stair[i][9] = stair[i - 1][8] % MOD;
                }

                else {
                    stair[i][j] = stair[i - 1][j - 1] + stair[i - 1][j + 1] % MOD;
                }
            }
        }

        long result = 0L;
        for (int i = 0; i < 10; i++) {
            result += stair[N][i];
        }

        return result;
    }
}

이상으로, 백준 10844 계단 오르기 문제 해결 과정 정리를 마치겠습니다.

감사합니다.!

 

문제 출처:

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