[백준 java] 11057 - 오르막 수

---

오르막 수 만들기

1112 1234 1345 이런식으로 인접한 숫자가 같거나 점점 오르는 형태의 수여야한다.

따라서 첫번 째 수에따라 만들 수 있는 수가 달라진다.

 

두 자리 수를 만들때

첫번째 숫자가 1이면  1 2 3 4 5 6 7 8 9 를 붙여 9개의 숫자를 만들 수 있고

첫번째 숫자가 4이면 44 45 46 47 48 49 6개 숫자를 만들 수 있다

 

세 자리 숫자를 만들때 

만약 첫 숫자가 0이면 뒤에 모든 숫자가 올 수 있으니 

두자리 숫자의 전체 갯수 55개의 숫자가 올 수 있고

첫 숫자가 1이면 55에서 두번 째 자리 숫자가 0이 올 수 없다 

따라서 0으로 만들 수 있는 두자리 수를 다 빼줘야한다.

 

위 연산을 계산하기 위해 2차원 배열 dp를 만들었고

dp[ i ][ j ]에서 i는 i자릿수,  j는 i자릿수 j번째 숫자를 나타낸다

 

 

3자리로 만들 수 있는 전체 오르막 수 

9 : 55 
8 : 45 +10 dp[2][9]
7 : 36 +9 
6 : 28 +8
5 : 21 +7
4 : 15 +6
3 : 10 +5
2 : 6  +4
1 : 3 +3
0 : 1 +2 dp[2][1]

 

 

dp[2][1]을 구하기 위해서 dp[1][0] + dp[1][1] 을 더해야한다.

따라서 점화식은 아래와 같다.

dp[i][j] = dp[i][j-1] + dp[i-1][j]

 

주의할 점

1. 계산 한 수에 10007을 나눈 후 나머지를 저장하자.

2. 역수에서 빼는 순서 (55-10 > 45-9) 가 아닌 더해가는 순서로 계산

( 10007이상의 수는 나머지로 계산되므로 주의)

---

// 오르막 수
// https://www.acmicpc.net/problem/11057

import java.util.Scanner;

public class B11057 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[][] dp = new long[1001][10];
        long[] sum = new long[1001];
        sum[1] = 10;
        for(int i =0; i<10; i++){
            dp[1][i] = 1;
        }

        for(int i=2; i<=N; i++){
            dp[i][0] = 1;
            sum[i] = dp[i][0];
            for(int j=1; j<10; j++){
                dp[i][j] =  (dp[i][j-1] + dp[i-1][j])%10007;
                sum[i] += dp[i][j];
            }
        }
        System.out.println(sum[N]%10007);
    }
}