https://www.acmicpc.net/problem/10844
문제
> 45656이란 수를 보자.
> 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
> N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.접근
dp를 이차원 벡터로 선언해 자릿수, 올 수있는 수의 조합으로 만든다.
예를 들어 N이 4라고 하면 첫자리엔 0이 올수 없으므로 일단 dp(1)(?)에 대해 ?엔 1부터 9까지 올 수 있다.
그래서 먼저 반복문으로 처리해주고 각각 1가지씩 되는거니까 1을 가진다.
각각의 dp1,1부터 9에 대해 다음자리에 올 수 있는 수를 구한다.
dp2,?에 대해 ?가 0이면 -1 했을때 음수이므로 +1했을 때만 계단수로가질 수 있고 ?가 9면 +1하면 10이므로 -1했을 때만 가질수 있다.
이 둘을제외하곤 -1, +1을 가질 수있다.
가능한 개수를 구하는건 반대로 생각한다. 트리 dp문제에서 했던것 처럼 예를들어 dp(2)(0)을 만들 수 있는건
dp(1)(1)에서 1뺀거만 가능하니까 수식으로 쓰면
dp(2)(0)+dp(1)(1) 즉 j가 0일때만 dp(i)(j) += dp(i-1)(j+1)이다.
j가 9일 떈 dp(i)(j) += dp(i-1)(j-1)이 된다.
이렇게 입력받은 길이 4에대해 dp(4)(9)까지 다 입력을 받은뒤 최종적으로 끝자리에 0부터 9까지 올 수 있는 수를 다 더해 주면 해당 자리수에서 가능한 계단수의 개수가 나온다.
문제해결
> 자릿수, 끝 수를 가지는 dp 벡터를 이차원으로 선언해준다.
> 맨 앞자리엔 0이 못오므로 dp1에 대해 1부터9까지 미리 지정해준다.
> 두번째 자리부터 반복문을 통해 입력받은 N번째 자리까지 반복하며 0부터 9까지 올 수 있는 수를 탐색한다.
> j가 0일땐, 1에서 빼서 0으로 되는것 뿐이고 9면 8에서 더해서 오는것 뿐이므로 이를 반대로 생각해 j+1과 j-1의 가짓수를 더해준다.
> 이외엔 둘다 더해준다. 마지막으로 1,000,000,000로 각 결과들을 나눠준다.
> dp(N)(9)까지 모두 구한 뒤 이를 0부터 9까지 다 더해준다. N이 1일 때를 생각해보면 한자릿수 일때 가능한 개수는 9개 즉 1부터 9까지이다. 이와 같은 원리로 0부터9까지 더해준다.
> 더해준 결과를 문제조건에 맞게 10억으로 모듈러연산을 하고 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int Mod = 1000000000;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<vector<long long>> dp(N + 1, vector<long long>(10, 0));
for(int i = 1; i <= 9; i++) dp[1][i] = 1;
for (int i = 2; i <= N; i++)
{
for (int j = 0; j <= 9; j++)
{
if (j == 0) dp[i][j] += dp[i - 1][j + 1];
else if (j == 9) dp[i][j] += dp[i - 1][j - 1];
else
{
dp[i][j] += dp[i - 1][j - 1];
dp[i][j] += dp[i - 1][j + 1];
}
dp[i][j] %= Mod;
}
}
long long rst = 0;
for (int i = 0; i <= 9; i++)
{
rst += dp[N][i];
}
cout << rst % Mod << '\n';
}
후기
길이를 짧게 해서 경우를 모두 따져 따라갔지만 규칙찾는게 복잡했다. 계속 노려보다가 전에 했던 트리문제가 생각이 났다. 비슷한 맥락이었는데 현재 계산해야 될 값을 구하기 위해 반대로 어떤값에서 이 값까지 올 수 있나를 따져봐야 풀리는 것이다. 굉장히 어렵다. dp
