[BOJ] 백준 10844번 - 쉬운 계단 수

문제

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

10844번: 쉬운 계단 수

 

• 계단 수 : 인접한 모든 자리의 차이가 1인 수의 나열 (0으로 시작하는 수 제외)
• 입력 : 첫째 줄에 N이 주어진다. (1<=N<=100)
• 출력 : 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력
  *이런 출력 조건이 있을 경우, DP테이블에 N이전 값들을 계산하는 과정에서 매번 값들에 1,000,000,000 나머지 연산을 취해줘야 최종 결과값이 바르게 구해짐.

 

풀이

점화식을 파악하기 위해 N=1, N=2, N=3 인 경우 가능한 계단 수를 구해보면 아래와 같다.

이전 차례의 계단수의 마지막 수가 0, 9일 경우 예외 발생

N일 경우 가능한 계단수 개수는 앞서 구한 N-1일 경우 가능한 계단수들의 마지막 값에 +1, -1값을 추가한 것이기 때문에, <길이가 N일 때 마지막 수가 L인 계단수의 개수 = N-1일 때 마지막 수가 L-1인 계단수 개수 + N-1일 때 마지막 수가 L+1인 계단수 개수> 라는 걸 알 수 있다.

<길이가 N일 때, 마지막 수가 L인 계단수 개수>
dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]               ex) dp[2][1] = dp[1][0] + dp[1][2]

 

그러나 N-1일 때 가능한 계단 수들 중 마지막 수가 0일 경우 (ex: 10, 210 등) 0과의 차이가 1인 수는 -1, 1인데 -1은 올 수가 없으므로 다음 N일 때 가능한 계단 수에서 해당 수의 끝자리에는 1만 추가할 수 있다.
같은 이유로 마지막 수가 9일 경우 9와의 차이가 1인 수는 8, 10인데 10은 올 수가 없으므로 끝자리에 8만 추가할 수 있다.

마지막 수가 0일 경우 / 9일 경우 / 그외 경우 처리 로직은 아래와 같다. 

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

 

이를 최대한 하나의 점화식 구문으로 줄이면 아래와 같이 쓸 수 있다.

long[][] dp = new long[101][11];

// ...생략

for (int i = 2; i <= n; i++) {
    dp[i][0] = dp[i - 1][1];
    for (int j = 1; j <= 9; j++) {
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
    }
}

 

dp[i][10] 값은 값이 새로 저장되지 않고 계속 0인 채로 있으므로, dp[i][9] 값을 구하기 위해 dp[i-1][8] + dp[i-1][10] 을 참조해도 무조건 dp[i-1][8] 값만 들어오게 된다. dp[i][10] 참조 시 ArrayIndexOutOfBoundsException 발생을 막기 위해 2차원 배열의 크기를 [10]에서 [11]으로 늘려 0~10 까지의 인덱스를 사용할 수 있도록 해둬야 한다.

dp[i][0] 값을 구하는 경우까지 점화식 for문에 포함시켜버리면 dp[i-1][-1] + dp[i-1][0] 로 접근 불가능한 -1인덱스를 참조하려 하기 때문에 이 경우는 for문 밖으로 따로 빼준다.

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // DP 테이블 dp[길이][마지막숫자]
        long[][] dp = new long[101][11];

        // dp[1][마지막숫자] 값 초기화
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }

        // DP Bottom-Up
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][1];
            for (int j = 1; j <= 9; j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
            }
        }
        
        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i];
        }
        System.out.println(sum % 1000000000);
    }
}

최종 값을 출력하기 위한 합계 for문에서는 길이가 N일 때 마지막 숫자가 L인 계단수 들의 개수를 모두 합해주는데, 이때 마지막 수가 0~9경우를 전부 합해줘야 한다. 1~9인 경우만을 합하지 않게 주의