[백준][10844] 쉬운 계단 수
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
입력 1
1
출력 1
9
입력 2
2
출력 2
17
1. 문제 설명
일단 1의 자리 숫자(1~9)는 뒤나 앞에 따라오는 숫자가 없으니 계단 수라고 가정한다.
예를 들어
n=2
일 경우,dp[2][1]
에는10
과12
가 해당되기 때문에dp[2][1] = 2
,dp[2][2]
일 경우21
,23
이 해당되기 때문에dp[2][2] = 2
.. 이런식으로dp[2][9]
까지 진행한다.
n=3
일 경우,dp[3][1]
에는101
,121
,123
가 해당되고,dp[3][1] = 3
,dp[3][2]
일 경우212
,232
,234
가 해당되기 때문에dp[3][2] = 3
.. 이런식으로dp[3][9]
까지 진행한다.쉽게 말하자면
dp[이부분][]
은 수의 길이(자릿수)를 의미하고dp[][이부분]
은 최상위 자릿수를 의미한다.
dp[2][3]
일 경우에dp[3][]
는 3자리수(100~999)를 의미,dp[3][3]
은 숫자3XX
를 의미한다. (XX
는dp[2][2]
와dp[2][4]
를 넣어주면 된다.dp[2][2]
를 붙이자면321
,323
이 된다.)
하.지.만.
- 그림에서 보다싶이 실제 값은
dp[2][1] = 2
가 아니고dp[2][1] = 1
이다.
왜 2가 아닐까? 싶겠지만 이걸 이해하여 구현한 사람이 대단하다는 생각이 든다.
- 그림에서와 같이
n=2
에서[1]
배열을 위에 설명한대로 대입하면10
,12
가 만들어진다. 총 2개지만, 하지만 0으로 시작할 수 없어n=1
일 때[0]
부분에 개수를0
으로 설정했기 때문에 실제n=1
일 때[2]
의1
값만 들어왔다. - 하지만
n=2
일 때[0]
배열을 보면n=1
일 때[1]
의1
값이 들어온 것이 보인다. 실제 위에 설명한대로 숫자를 만들면01
이 되는데, 문제에선 ‘0으로 시작하는 숫자는 세지 않는다’고 했다. 여기가 핵심이다.
이건 거꾸로 보게되면10
이 된다. - 뒤쪽이 0으로 끝나는 숫자는 이런식으로 배열
[0]
에서 세도록 구현됐다.
마지막으로 그림을 보면
[0]
과[9]
는 앞,뒤로 가져올 배열이 없다. 그래서 해당 배열들은 각각[1]
과[8]
에서만 값을 가져올 수 있도록 구현해야 한다.[점화식]
[0]
일 때 :dp[i][0] = dp[i-1][1]
[9]
일 때 :dp[i][9] = dp[i-1][1]
그 외의 숫자일 때 :dp[i] = dp[i-1][j-1] + dp[i-1][j+1]
문제에서 1,000,000,000로 나눈 나머지를 구하라고 하였으니,
점화식 뒤에% 1000000000
를 적어주면 끝.
2. 소스 코드
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000000;
int main() {
int n;
cin >> n;
vector< vector<long long> > dp(n + 1, vector<long long>(11, 0));
for (int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][1] % MOD;
dp[i][9] = dp[i - 1][8] % MOD;
for (int j = 1; j <= 8; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % MOD;
}
}
long long sum = 0;
for (int i = 0; i < 10; i++) {
sum += dp[n][i] % MOD;
}
cout << sum % MOD<< endl;
return 0;
}