정답률 47퍼센트의 dp 문제 오르막 수 이다.
앞서 글을 썼던 쉬운계단 수 문제와 굉장히 비슷한 문제이기 때문에 정답률이 높은 것이라는 추측을 한다.
차이점이 있다면 쉬운 계단 수는 마지막 자리에 있는 수에서 반드시 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) 정해져있기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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);
}
|
'Algorithm' 카테고리의 다른 글
백준 2156 포도주 시식 Java (0) | 2019.04.10 |
---|---|
백준 9465 스티커 Java (0) | 2019.04.10 |
백준 10844 쉬운 계단 수 Java (0) | 2019.04.10 |
백준 2193 이친수 Java (1) | 2019.04.10 |
백준 9095 1, 2, 3 더하기 Java (0) | 2019.04.09 |