<Algorithm> 198. 오르막수(BJO)

1. 11057번 오르막수(BJO)

   사용 알고리즘 : DP 

• 2차원 배열을 쓰는 DP 기본문제, 규칙을 찾아내는데 좀 오래걸렸던 것 같다.

• dp 배열안에 꼭 출력하는 정답이 있어야하는 것은 아니다 라는 걸 깨달았다. (이문제처럼 DP값을 모두 더해도 된다.[다음 0번째도 가능]) 

• 또 로직에 이상없었는데 자꾸 틀려서 의아했는데 mod를 마지막에 안해주었다... mod는 중간과 끝 모두 해주어야 한다. !!!

문제에 대한 접근&생각

1. N은 1000, 시간제한 1초 그리고 길이가 1000인 숫자 -> 완전탐색 시간초과! -> DP!
2. 규칙을 찾자 -> 그려보면 한단계씩 대각선 방향으로 줄어듬 -> N이 2일때 55를 잘보면 N(N+1)/2 -> 10+9+8+7 ~~ +1
3. 즉 이전에 DP값에서 하나씩 줄인 합계와 같음 -> ex) N=2 1*9 + 1*8 + 1*7 ~~ +1*1 
4. 현재 DP에는 이전값의 합을 저장하는 점화식! -> dp[길이][0] += dp[길이][0~9]
5. 출력은 길이에 해당하는 모든 값을 더함! 

코드 

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();
        int mod = 10_007;
        /************************
         * DP를 이용해 해당 길이에 합한
         * 결과값을 저장하여 그 다음
         * 값을 도출한다.
         ************************/
        long[][] dp = new long[n+1][10];
        Arrays.fill(dp[1], 1);
        int start = 2;
        while (start <= n) {
            for(int i = 0; i < 10; i++) {
                for(int j = i; j < 10; j++) {
                    dp[start][i] += dp[start-1][j]%mod;
                }
            }
            start++;
        }
        long ans = Arrays.stream(dp[n]).sum();
        System.out.println(ans%mod);
    }
}