백준 11057 오르막 수 Java

정답률 47퍼센트의 dp 문제 오르막 수 이다. 

 

백준 10844 쉬운 계단 수 Java

앞서 글을 썼던 쉬운계단 수 문제와 굉장히 비슷한 문제이기 때문에 정답률이 높은 것이라는 추측을 한다.

차이점이 있다면 쉬운 계단 수는 마지막 자리에 있는 수에서 반드시 1차이가 나야했지만

오르막 수는 자신을 포함한 자신보다 큰수여야 한다. 예를 들면 마지막 자리 수가 8이면 8,9가 해당 된다.

 

쉬운 계단 수와 똑같이 점화식을 세우면

dp[n][마지막자리 수] = dp[n-1][마지막자리 수 ~ 9] 이다.

쉬운 계단 수와 다른 점이 있다면 쉬운 계단 수는 2개여서

반복문 없이 dp[n]에 더하면 됐지만 오르막 수는 범위이고 그 범위가 항상 달라지므로

반복문을 써서 더해주면 된다.

 

그렇게 for문을 3중첩해서 문제를 풀면 되는데 3중첩이라고 해서O(n^3)은 아니다.

왜냐면 2번째, 3번째 for문은 끝나는 조건이 <10 또는 <=9로(0~9) 정해져있기 때문이다.

 

public static void main(String[] args) {
        final int mod = 10007;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long [][] dp = new long[n+1][10];
 
        for(int i=0; i<10; i++)
            dp[1][i] = 1;
 
        for(int i=2; i<=n; i++) {
            for(int j=0; j<10; j++) {
                for(int k=j; k<10; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= mod;
                }
            }
        }
        long answer = 0;
        for(int i=0; i<10; i++)
            answer += dp[n][i];
 
        System.out.println(answer%mod);
    }