발상
문제에서 제한 건 대상을 보면 알 수 있지만 수가 아닌 문자열로 취급하고 접근하는게 더 편하다. 우선 인자부터 찾아보자. 당연히 첫번째 인자는 수의 자릿수다. 하지만 이것만으론 문제를 풀기 어렵다. 사실 이 문제에는 숨겨진 두번째 인자가 있다. 바로 수의 마지막 자리의 숫자다. 이전 숫자와 1차이나는 숫자만 추가할 수 있기 때문에 마지막 숫자를 기준으로 합을 구하는게 편리하다.
점화식
마지막에 답을 구할 때 0으로 시작하는 경우는 제외하고 합계를 구해야 한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1e9;
int main() {
int n; cin >> n; vector<vector<int>> dp(n + 1, vector<int>(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++) {
int s1 = j > 0 ? dp[i - 1][j - 1] : 0;
int s2 = j < 9 ? dp[i - 1][j + 1] : 0;
dp[i][j] = (s1 + s2) % mod;
}
}
int s = 0;
for (int i = 1; i < 10; i++) {
s += dp[n][i];
s %= mod;
}
cout << s;
return 0;
}이 문제에서 배워야할 점은 문제를 분석하고 인자를 스스로 정하는 법이다. 순차적으로 자릿수를 늘리며 이전 최적값을 계산하는 것은 여러 번 나왔던 기법이지만 문제에서 직접 언급되지 않은 인자를 찾아 활용했던 점이 중요하다. 물론 이 정도도 아직 충분히 유추 가능한 범위지만 가면 문제 난이도가 올라갈수록 인자를 교묘하게 숨기기도 하고 점화식 자체도 복잡해지기 때문에 충분한 연습이 필요하다