공부 136일차: 백준 11057번 오르막 수 자바 java

11057 오르막 수

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

11057번: 오르막 수

 

 

 

 

---

백준 11057번 문제 오르막 수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

아래의 1~10을 오른쪽에 써서 아래로 10,9,..1도 가능

 

이렇게 구해보면 규칙을 발견할 수 있다

표로 정리한 규칙은 다음과 같다

n\i	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	(0~9) 10	(1~9) 9	(2~9) 8	(3~9) 7	(4~9) 6	(5~9) 5	(6~9) 4	(7~9) 3	(8~9) 2	(9) 1
3	(0~9) 55	(1~9) 45	(2~9) 36	(3~9) 28	(4~9) 21	(5~9) 15	(6~9) 10	(7~9) 6	(8~9) 3	(9) 1

따라서

dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][1] = dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][2] = dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][3] = dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][4] = dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][5] = dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][6] = dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][7] = dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][8] = dp[n-1][8]+ dp[n-1][9]
dp[n][9] = dp[n-1][9]

라는 식을 구할 수 있다

이때 우리가 구해야 하는 수는 dp[n][0] + … + dp[n][9] 이다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        final int MOD = 10_007;
        int[][] dp = new int[n+1][10];
        
        for(int i = 0; i < 10; i++) {
            // 1자리일 때 0~9로 끝나는 숫자는 모두 1개씩
            dp[1][i] = 1;
        }
        
        for(int i = 2; i < n+1; i++) {
            for(int j = 0; j < 10; j++) {
                for(int k = j; k < 10; k++) {
                    // 오버플로우를 막기 위한 나머지 연산
                    dp[i][j] += (dp[i-1][k]) % MOD;
                }
            }
        }
        
        int sum = 0;
        for(int i = 0; i < 10; i++) {
            sum += dp[n][i];
        }
        
        // 오버플로우를 막기 위한 나머지 연산
        System.out.println(sum%MOD);
 
    }
 
}
 

 

과정 설명은 다소 복잡해보이지만 코드로는 어렵지 않다

 

 

 

---