10844. 쉬운 계단 수 (자바, Java)

 

문제 자체의 발상은 크게 어렵지 않았다. 자릿수를 하나씩 늘려나가면서, 가장 마지막 자릿수에 숫자를 붙이는 식으로 생각하였다.

문제는 엉뚱한 곳에서 일어났는데, n이 100까지 가는, 100자리 수가 대상이었기에 경우의 수를 따지면서 숫자가 굉장히 커졌다. 예제가 부실하여 직접 계산하거나 전체를 돌려볼 수 밖에 없었는데, 그냥 무지성 제출했던게 화근이 되었다.

 

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

public class Main {

    static Double[][] dp; // 마지막 수와 자릿수에 따른 계단수의 갯수를 저장할 배열.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new Double[10][n];
        dp[0][0] = 0d;
        for (int i=1; i<=9; i++) {
            dp[i][0] = 1d;
        }
        long ans = 0;
        for (int i=0; i<10; i++) {
            ans+=stair(i, n-1);
        }
        System.out.println(ans%1000000000);
    }

    // 재귀를 통해 계단수를 구하는 메서드. k=직전 자리의 숫자, n=자릿수.
    static double stair(int k, int n) {
        if (dp[k][n]==null) {
            if (k==0) {
                dp[k][n] = stair(1, n-1);
            }
            else if (k==9) {
                dp[k][n] = stair(8, n-1);
            }
            else {
                dp[k][n] = stair(k-1, n-1) + stair(k+1, n-1);
            }
        }
        return dp[k][n];
    }

}

제출하자 틀렸다고 나왔고, Main 메서드의 마지막 반복문을 이중포문으로 바꾸고, 반복출력하면서 n=100까지 전수조사를 하였다. 그러자 특정 범위부터 음수가 나오기 시작했다.

중간에 overflow가 일어난다는 것을 확인했고 (애초에 자연수이상의 누적합으로 구성되는데, 음수가 나올리없다),

재귀의 return값을 나눠주면서 해결하였다. dp에 저장되는 값이 overflow되지는 않지만, 각각의 값을 반복해 더해주면서 결과값인 ans가 overflow가 일어나는 것.

 

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

public class Main {

    static Long[][] dp; // 마지막 수와 자릿수에 따른 계단수의 갯수를 저장할 배열.
    final static long mod = 1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new Long[10][n];
        dp[0][0] = 0L;
        for (int i=1; i<=9; i++) {
            dp[i][0] = 1L;
        }
        long ans = 0;
        for (int i = 0; i < 10; i++) {
            ans += stair(i, n - 1);
        }
        System.out.println(ans%mod);
    }

    // 재귀를 통해 계단수를 구하는 메서드. k=직전 자리의 숫자, n=자릿수.
    static long stair(int k, int n) {
        if (dp[k][n]==null) {
            if (k==0) {
                dp[k][n] = stair(1, n-1);
            }
            else if (k==9) {
                dp[k][n] = stair(8, n-1);
            }
            else {
                dp[k][n] = stair(k-1, n-1) + stair(k+1, n-1);
            }
        }
        return dp[k][n] % mod;
    }
}