Algorithm/백준
[백준] 11057번 오르막 수
sirius
2021. 3. 8. 11:18
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.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=0; k <= j; k++) {
dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007;
}
}
}
int sum = 0;
for(int i=0; i < 10; i++) {
sum += dp[N][i];
}
System.out.println(sum%10007);
}
}