풀이 아이디어

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.
1천 자리 수를 계산해야하기 때문에 수가 어마어마하게 클거라고 생각해서
java.math.BigInteger를 사용했다.

int[10] dp 배열을 생성해 n자리 수에서 끝에 자리에 따라서 가능한 경우의 수는

• __0 -> 10개 (0,1,2,3,4,5,6,7,8,9) -> dp[0]=i는 0~9까지 dp[i] 합
• __1 -> 9개 (1,2,3,4,5,6,7,8,9) -> dp[1]=i는 1~9까지 dp[i] 합
• __2 -> 8개 (2,3,4,5,6,7,8,9) -> dp[2]=i는 2~9까지 dp[i] 합
• __3 -> 7개 (3,4,5,6,7,8,9) -> dp[3]=i는 3~9까지 dp[i] 합
• __4 -> 6개 (4,5,6,7,8,9) -> dp[4]=i는 4~9까지 dp[i] 합
• __5 -> 5개 (5,6,7,8,9) -> dp[5]=i는 5~9까지 dp[i] 합
• __6 -> 4개 (6,7,8,9) -> dp[6]=i는 6~9까지 dp[i] 합
• __7 -> 3개 (7,8,9) -> dp[7]=i는 7~9까지 dp[i] 합
• __8 -> 2개 (8,9) -> dp[8]=i는 8~9까지 dp[i] 합
• __9 -> 1개 (9) -> dp[9]=i는 dp[9]

아래 그림으로 가능한 경우의 수를 정리했는데
n=2일 때 0~9까지 가능한 경우의 수를 합쳐 55
n=3일 때 0~9까지 가능한 경우의 수를 합쳐 220
n=4일 때 0~9까지 가능한 경우의 수를 합쳐 715

트러블슈팅

맞게 푼거 같은데 틀렸다고 해서 뭐가 문제지 싶었는데
dp[j] %= 10007을 해줘야 제대로 된 결과가 나왔다.
결국 dp[j]각각에 dp[j]%=10007을 해주고 마지막에 sumValue에도 sumValue%10007을
해줘야 정답이 되었다.
파이썬이나 c로 풀었던 다른 스터디원들은 마지막에 한번만 해줘도 정답이었다고 한다.
자바만 다른게 있나? 싶었다.

풀이 코드

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

public class _11057 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        if (n == 1){
            System.out.println(10);
            return;
        }

        BigInteger sumValue = new BigInteger("0");

        // dp=[10,9,8,7,6,5,4,3,2,1]로 초기화
        int[] dp = new int[10];
        for(int j=0;j<10;j++){
            dp[j] = 10-j;
        }

        // n-2번 반복
        for(int i=0;i<n-2;i++){
            // 9부터 0까지 역순으로 더해주기
            for(int j=8;j>=0;j--){
                dp[j] = dp[j] + dp[j+1];
                dp[j] %= 10007;
            }   
        }

        // 오르막수 개수를 저장하는 배열
        for(int j=0;j<10;j++){
            sumValue = sumValue.add(BigInteger.valueOf(dp[j]));
        }
        
        sumValue = sumValue.remainder(new BigInteger("10007"));

        System.out.println(sumValue);
    }
}