[JAVA] 백준, 11057번 오르막 수

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

 

해설

31%쯤에 오답으로 처리가 됐다.. 

분명 로직상으로는 맞다고 생각이 드는데... 이유를 모르겠어서 반례 케이스를 찾아봤다.

 

입력으로 n에 500을 넣으니 음수가 출력이 되고 있었다...?

분명 10007을 나누어 주었기 때문에 오버플로우가 발생하지 않을 것으로 생각했다.

 

오버 플로우를 해결하기 위해 int -> long으로도 해보았으나 똑같이 예외가 발생해서 BigInteger를 사용했다.

마지막에 값을 출력할 때만 BigInteger를 사용하면 된다.

 

dp는 풀 때마다 느끼지만 직접 그려보면서 규칙을 찾아야하는 것 같다.

 

ex) 3자리 수

• 1xx : 첫번째 자리에 1이 들어가므로 2번째 자리에 1 ~ 9가 들어갈 수 있다.
• 2xx : 첫번째 자리에 2가 들어가므로, 2번째 자리에 1을 제외한 2 ~ 9가 들어갈 수 있다.

위 규칙을 적용한 사진은 아래와 같다.

코드

DP 1차원 자리의 10번 인덱스에 저장하는 값은 자리수마다 경우의 수를 저장한다.

예를 들어, 2자리 수로 만들 수 있는 경우의수는 총 45개(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)을 저장한다.

마지막에 N에 대한 경우의수를 반환할 때는 1부터 N까지의 가능한 모든 경우의 수를 더해서 반환한다.

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

public class Main {

    static int[][] 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 int[n + 1][11];

        for (int i = 0; i < 10; i++) {
            dp[1][i] = i;
        }
        dp[1][10] = 10;
        if (n == 1) {
            System.out.println(dp[1][10]);
            return;
        }

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

        System.out.println(solution(n));
    }

    static BigInteger solution(int n) {
        for (int i = 3; i <= n; i++) {
            dp[i][1] = dp[i - 1][10];
            int sum = dp[i][1];
            for (int j = 2; j < 10; j++) {
                dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1];
                sum += dp[i][j];
            }
            dp[i][10] = sum % 10007;
        }

        BigInteger result = BigInteger.ZERO;
        for (int i = 1; i <= n; i++) {
            result = result.add(BigInteger.valueOf(dp[i][10]));
        }

        return result.mod(BigInteger.valueOf(10007));
    }
}