문제풀이/백준
[백준]10844: 쉬운 계단 수 - JAVA
빈둥벤둥
2021. 2. 11. 18:51
[백준]10844: 쉬운 계단 수
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이
DP문제는 진짜진짜 많이 풀어봐야 할 것 같다. 아직 완전히 이해하고 풀 수준이 안되는 것 같다.
이 문제는 dp함수를 2차원 배열로 만들었다. dp배열 의미하는 뜻은 dp[길이][마지막 자리수가 계단이 되는 경우의 수] 이다.
n이 1 일때는 다음과 같다. n이 1일때 0은 결과에 포함되지 않으므로 계산하지 않는다.
| dp[1][1] | 1 | 길이가 1일이고 끝자리의 수가 1일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][2] | 1 | 길이가 1일이고 끝자리의 수가 2일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][3] | 1 | 길이가 1일이고 끝자리의 수가 3일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][4] | 1 | 길이가 1일이고 끝자리의 수가 4일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][5] | 1 | 길이가 1일이고 끝자리의 수가 5일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][6] | 1 | 길이가 1일이고 끝자리의 수가 6일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][7] | 1 | 길이가 1일이고 끝자리의 수가 7일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][8] | 1 | 길이가 1일이고 끝자리의 수가 8일때 앞에 올 수 있는 수는 없으므로 1이다. |
| dp[1][9] | 1 | 길이가 1일이고 끝자리의 수가 9일때 앞에 올 수 있는 수는 없으므로 1이다. |
n이 2일때는 다음과 같다.
| dp[2][0] | dp[1][1] | 길이가 2이고 끝자리의 수가 0일때는 앞에 올 수 있는 수는 1밖에 없으므로 dp[1][1]이다. |
| dp[2][1] | dp[1][0] + dp[1][2] | 길이가 2이고 끝자리의 수가 1일때는 앞에 올 수 있는 수는 0과 1이므로 dp[1][0] + dp[1][2]이다. |
| dp[2][2] | dp[1][1] + dp[1][3] | 길이가 2이고 끝자리의 수가 2일때는 앞에 올 수 있는 수는 1과 3이므로 dp[1][1] + dp[1][3]이다. |
| dp[2][3] | dp[1][2] + dp[1][4] | 길이가 2이고 끝자리의 수가 3일때는 앞에 올 수 있는 수는 2과 4이므로 dp[1][2] + dp[1][4]이다. |
| dp[2][4] | dp[1][3] + dp[1][5] | 길이가 2이고 끝자리의 수가 4일때는 앞에 올 수 있는 수는 3과 5이므로 dp[1][3] + dp[1][5]이다. |
| dp[2][5] | dp[1][4] + dp[1][6] | 길이가 2이고 끝자리의 수가 5일때는 앞에 올 수 있는 수는 4과 6이므로 dp[1][4] + dp[1][6]이다. |
| dp[2][6] | dp[1][5] + dp[1][7] | 길이가 2이고 끝자리의 수가 6일때는 앞에 올 수 있는 수는 5과 7이므로 dp[1][5] + dp[1][7]이다. |
| dp[2][7] | dp[1][6] + dp[1][8] | 길이가 2이고 끝자리의 수가 7일때는 앞에 올 수 있는 수는 6과 8이므로 dp[1][6] + dp[1][8]이다. |
| dp[2][8] | dp[1][7] + dp[1][9] | 길이가 2이고 끝자리의 수가 8일때는 앞에 올 수 있는 수는 7과 9이므로 dp[1][7] + dp[1][9]이다. |
| dp[2][9] | dp[1][8] | 길이가 2이고 끝자리의 수가 9일때는 앞에 올 수 있는 수는 8밖에 없으므로 dp[1][8]이다. |
여기서 중요한 부분은 끝자리의 수가 0, 9일때이다. 나머지 수들은 모두 자신의 값 -1, +1한 값들이 앞에 올 수 있지만 0은 -1한 값이, 9는 +1한 값이 앞에 올 수 없으므로 따로 처리해 주어야 한다.
그리고 문제의 조건대로 값을 계속 나누어 줘야 하는것도 잊으면 안된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import java.util.*;
public class Main {
static long mod = 1000000000;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long[][] dp = new long[n + 1][10];
for(int i = 1; i <= 9; i++) {
dp[1][i] = 1; //1자리 수의 i번째 수가 계단이 되는 경우는 한가지 밖에 없으므로 초기화.
}
for(int i = 2; i <= n; i++) {
for(int j = 0; j < 10; j++) {
if(j == 0) dp[i][j] = dp[i - 1][j + 1] % mod; //끝 자리가 0일때는 앞에 올 수 있는 수가 1밖에 없다.
else if(j == 9) dp[i][j] = dp[i - 1][j - 1] % mod; //끝 자리가 9 일때는 앞에 올 수 있는 수가 8밖에 없다.
else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
}
}
long result = 0;
for(int i = 0; i < 10; i++ ) {
result += dp[n][i];
}
System.out.println(result % mod);
}
}
|
cs |