728x90
728x90
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 1
1
예제 출력 1
9
예제 입력 2
2
예제 출력 2
17
알고리즘 분류
- 다이나믹 프로그래밍
문제 출처
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
문제 해결 방법
- DP를 이용하여 문제를 해결하였다.
점화식 구하기
- 이 문제의 해결을 위한 핵심은 다음과 같다.
① 길이가 N - 1 인 숫자의 마지막 자리 숫자(X )가 0 일 경우, 길이가 N 인 숫자는 그 뒤에 1 만 붙일 수 있다. (예 : 01)② 길이가 N - 1 인 숫자의 마지막 자리 숫자(X )가 9 일 경우, 길이가 N 인 숫자는 그 뒤에 8 만 붙일 수 있다. (예 : 98)③ 길이가 N - 1 인 숫자의 마지막 자리 숫자(X )가 1 ~ 8 일 경우, 길이가 N 인 숫자는 그 뒤에 X - 1 또는 X + 1 을 붙일 수 있다. (예: 10, 12 또는 87, 89) |
- 우선 한 자릿수(
N = 1
)는1
,2
,3
,4
,5
,6
,7
,8
,9
으로, 총 9가지가 있다. N
이 각각1
,2
,3
일 때, 위의 조건을 이용하여 쉬운 계단 수를 구해보자.
N = 1
일 경우
- 총 9가지
N | X |
||||||||
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
N = 2
일 경우
- 총 17가지
N | X | ||||||||
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2 | 10 | 21 | 32 | 43 | 54 | 65 | 76 | 87 | 98 |
11 | 23 | 34 | 45 | 56 | 67 | 78 | 89 |
N = 3
일 경우
- 총 32가지
N | X | ||||||||
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2 | 10 | 21 | 32 | 43 | 54 | 65 | 76 | 87 | 98 |
11 | 23 | 34 | 45 | 56 | 67 | 78 | 89 | ||
3 | 101 | 210 | 321 | 432 | 543 | 654 | 765 | 876 | 987 |
212 | 323 | 434 | 545 | 656 | 767 | 878 | 989 | ||
110 | 212 | 343 | 454 | 565 | 676 | 787 | 898 | ||
112 | 234 | 345 | 456 | 567 | 678 | 789 |
- 따라서 위의 조건을 이용하여 점화식을 구하면 다음과 같다.
DP 테이블 만들기
- DP 테이블은
dp[N][X]
와 같이 정의한다. (N
: 자릿수,X
: 마지막 자리 숫자) - 100자리의 수까지 계속 누적하면서 DP 테이블을 채워나가야 하기 때문에, 가장 큰 자료형(
unsigned long long
)을 사용한다.
ULL dp[101][10];
- 문제에서
100,000,000
으로 나눈 나머지를 출력하려고 했으므로, 위에서 구한 점화식을 다음과 같이 수정해준다.
- 코드로 표현하면 다음과 같다.
int Solution(int n) { ULL result = 0; // 한 자릿수의 경우 (A = 1) for (int i = 1; i <= 9; i++) { dp[1][i] = 1; } // 두 자릿수 이상인 경우 (A >= 2) for (int i = 2; i <= n; i++) { dp[i][0] = dp[i - 1][1]; // 마지막 숫자가 0인 경우, 그 뒤에 1만 올 수 있다. for (int j = 1; j <= 8; j++) { dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD; // 마지막 숫자가 1~8인 경우, 그 뒤에 숫자가 2개 (j - 1 또는 j + 1) 올 수 있다. } dp[i][9] = dp[i - 1][8]; // 마지막 숫자가 9인 경우, 그 뒤에 8만 올 수 있다. } for (int i = 0; i <= 9; i++) { result += dp[n][i]; } result %= MOD; return result; }
코드
#include <iostream> using namespace std; #define MOD 1000000000 using ULL = unsigned long long; int N; ULL dp[101][10]; // dp[N][X], N : 자릿수, X : 마지막 자리 숫자 void Input() { cin >> N; } int Solution(int n) { ULL result = 0; // 한 자릿수의 경우 (A = 1) for (int i = 1; i <= 9; i++) { dp[1][i] = 1; } // 두 자릿수 이상인 경우 (A >= 2) for (int i = 2; i <= n; i++) { dp[i][0] = dp[i - 1][1]; // 마지막 숫자가 0인 경우, 그 뒤에 1만 올 수 있다. for (int j = 1; j <= 8; j++) { dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD; // 마지막 숫자가 1~8인 경우, 그 뒤에 숫자가 2개 (j - 1 또는 j + 1) 올 수 있다. } dp[i][9] = dp[i - 1][8]; // 마지막 숫자가 9인 경우, 그 뒤에 8만 올 수 있다. } for (int i = 0; i <= 9; i++) { result += dp[n][i]; } result %= MOD; return result; } void Output() { cout << Solution(N) << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Input(); Output(); return 0; }
채점 결과

참고
- [단계별로 풀어보기] > [동적 계획법 1]
- 실버I
728x90
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ-11722][C++] 가장 긴 감소하는 부분 수열 (0) | 2022.12.14 |
---|---|
[BOJ-16499][C++] 동일한 단어 그룹화하기 (2) | 2022.12.14 |
[BOJ-11053][C++] 가장 긴 증가하는 부분 수열 (0) | 2022.12.14 |
[BOJ-2156][C++] 포도주 시식 (0) | 2022.12.13 |
[BOJ-1463][C++] 1로 만들기 (0) | 2022.12.11 |
[BOJ-17427][C++] 약수의 합 2 (0) | 2022.12.11 |
[BOJ-2579][C++] 계단 오르기 (0) | 2022.12.09 |
[BOJ-1932][C++] 정수 삼각형 (0) | 2022.12.08 |