boj)11057 - 오르막수
2020. 9. 19. 03:16ㆍPS/boj
import java.io.*;
public class boj_11057 {
static int[][] dp;
static final int mod = 10007;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp = new int[n+1][10];
for (int i = 0; i <= 9; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= j; k++) {
dp[i][j] += dp[i-1][k];
dp[i][j] %= mod;
}
}
}
long ans = 0;
for (int i = 0; i <= 9; i++) {
ans += dp[n][i];
}
System.out.println(ans % mod);
}
}
- 마지막 부분에 올 수 있는 수는 ? -> 0~9 까지이고 변수 L로 생각
- 그렇다면 앞에 올 수 있는 경우의 수는 ? -> L보다 같거나 작은 값들
- dp[n][L] :: 길이가 n인 수에서 L로 끝나는 경우의 수
- dp[n][L] = sigma( dp[n-1][K] ) :: 0 <= K <= L
- 이 점화식으로 dp를 채우고 정답은 sigma( dp[n][0] ~ dp[n][9] ) 이다 .
'PS > boj' 카테고리의 다른 글
boj)2156 - 포도주 시식 (0) | 2020.09.19 |
---|---|
boj)9465 - 스티커 (0) | 2020.09.19 |
boj)1309 - 동물원 (0) | 2020.09.19 |
boj)1149 - RGB 거리 (0) | 2020.09.19 |
boj)2225 - 합분해 (0) | 2020.09.18 |