안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅은 백준 10844번의 계단 오르기 문제를 해결한 과정을 정리하고자 합니다.
해당 문제는 N자리 숫자의 계단 수를 구하는 문제입니다.
1. 문제 해결 과정
1) n == 1일 때,
- 한자리 숫자의 경우 1 ~ 9까지 총 9개가 계단수입니다.
2) n == 2 일 때,
- 두 자리 숫자의 경우, 총 17개입니다.
12, 23, 34, 45, 56, 67, 78, 89 (8개)
10, 21, 32, 43, 54, 65, 76, 87, 98 (9개)
3) n == 3일 때,
- 세 자리 숫자의 경우, 총 32개입니다.
123, 234, 345, 456, 567, 678, 789 (7개)
987, 876, 765, 654, 543, 432, 321, 210 (8개)
101, 212, 323, 434, 545, 656. 767, 878, 989 (9개)
121, 232, 343, 454, 565, 676, 787, 898 (8개)
이 문제에서는 n번째 자리에 위치한 숫자는
(n - 1) 번째 자리 숫자보다 1 작은 수가 나올 수 있는 경우의 수 + (n -1) 번째 자리 숫자보다 1 큰 수가 나올 수 있는 경우의 수로
DP를 구현할 수 있습니다.
이를 그림으로 확인하면 다음과 같습니다.
따라서, 이를 알고리즘화 하면 아래의 코드로 구현할 수 있습니다.
stair[i][j] = stair[i - 1][j - 1] + stair[i - 1][j + 1]2. 주의할 점
하지만, 주의할 점은 0보다 작은 자연수는 없으므로 자리 숫자에 0이 있으면 경우의 수는 (위치한 자릿수 - 1)의 1 큰 수의 경우만 고려해야 합니다.
stair[i][0] = stair[i - 1][1]또한, 9는 9보다 1이 큰 한자리 숫자는 없으므로, (위치한 자리수 - 1)의 1 작은 수의 경우만 고려해야 합니다.
stair[i][9] = stair[i - 1][8]
마지막으로, 해당 알고리즘 결과를 제출하는데 여러 번 오답이 발생했습니다.
그 이유는, 최종 결과를 도출하는 과정에서 중간에 이미 long의 범위를 벗어나서 올바른 값을 도출하지 못했기 때문입니다.
(자바 long의 범위는 -2^63 ~ 2^63 -1)입니다.
해결책은 모듈러 연산을 적용하는 것입니다.
모든 경우의 수는 마지막 자릿수의 1부터 ~ 9까지의 경우를 더하면 완성이 됩니다. 이후, 10억으로 나눠도 되지만,
연산 가능 범위를 벗어날 수 있으므로, 모듈러 연산을 적용하여 각 배열에 저장할 때마다 MOD로 나머지 연산을 해주고
최종적으로 마지막 숫자들을 더한 후, 다시 MOD로 나머지 연산을 해주면 동일한 결과를 얻을 수 있습니다.
long result = 0L;
for (int i = 0; i < 10; i++) {
result += stair[N][i];
}(A + B) % p = ((A % p) + (B % p)) % p3. 최종 소스 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main10844 {
static final long MOD = 1000000000;
static int N;
static long[][] stair;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
stair = new long[N + 1][10]; // (n 자리수), (0 ~ 9)
long result = doStairDp();
System.out.print(result % MOD);
}
static long doStairDp() {
for (int i = 1; i<10; i++) {
stair[1][i] = 1; // 첫번째 자리수가 i 일때는 모두 1
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j < 10; j++) {
if (j == 0) {
stair[i][0] = stair[i - 1][1] % MOD;
}
else if (j == 9) {
stair[i][9] = stair[i - 1][8] % MOD;
}
else {
stair[i][j] = stair[i - 1][j - 1] + stair[i - 1][j + 1] % MOD;
}
}
}
long result = 0L;
for (int i = 0; i < 10; i++) {
result += stair[N][i];
}
return result;
}
}이상으로, 백준 10844 계단 오르기 문제 해결 과정 정리를 마치겠습니다.
감사합니다.!
문제 출처:
'Algorithm' 카테고리의 다른 글
| [Algorithm] 백준 2206 BFS 자바 풀이 (0) | 2023.04.08 |
|---|---|
| [Algorithm] 백준 2178, 1697 BFS 자바 풀이 (0) | 2023.04.07 |
| [Algorithm] 백준 2667, 1012 DFS 자바 풀이 (0) | 2023.04.07 |
| [Algorithm] DP - 백준2579 계단 오르기 (0) | 2023.01.06 |
| [Algorithm] 백준 11286번 풀이 (0) | 2022.12.28 |
