https://www.acmicpc.net/problem/11057
문제
> 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.
> 이때, 인접한 수가 같아도 오름차순으로 친다.
> 예를 들어, 2234와 3678, 11119는 오르막 수이지만,
2232, 3676, 91111은 오르막 수가 아니다.
> 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오.
> 수는 0으로 시작할 수 있다.접근
dp를 이차원 벡터로 선언하고 행을 자릿수, 열을 그 수로 끝나는 수라고 잡고 표를 그려보면 아래와같다.
1자리수 일 땐 끝에 뭐가오던 1가지씩 가능하므로 전부 1이고
자릿수 상관없이 0으로 끝나는 수도 1가지씩만 가능하다(0,000...)
이제 2,1을 보면 2자리수인데 1로 끝나는 수를 말하고 이는 01,11 이렇게 두개가있다. 즉 다시 말하면 2자리 인데 1로끝나는 거니까 ?1로 수를 잡고 ?에는 1보다 작은 수만 올 수 있다.
그럼 표에서 -1행에서 1보다 작은 애들의 수를 더한 값이된다.
그래서 2,2는 1,0과 1,1과 1,2을 더한 3이 되는 것이다.
이제 3,1을 보면 2,0과 2,1을 더한 값이된다.
3,2는 2,0과 2,1과 2,2를 더한 값이다.
둘 이 겹치는 부분이 생긴다. 2,0과 2,1
즉, 3,2는 3,1과 2,2의 합이라고도 할 수 있는 것이다.
따라서 이를 수식으로 써보면 dp(i)(j) = dp(i)(j-1) + dp(i-1)(j)라고 할 수 있다.
문제해결
> 각 자릿수와 끝나는 수 별로 가능한 경우를 저장할 이차원 벡터 dp를 만든다.
> 1,?와 ?,0은 모두 1개씩만 가능하므로 이를 1로초기화 해준다.
> 2자릿수 부터 1~9까지 끝나는 수를 위에서 유도한 공식으로 구한다.
문제에서 10007을 나눈 나머지를 따지라고 했으므로 dp값을 구할 때마다 이를 연산해준다.
> 각 자릿수의 총 가능한 경우의 수는 0부터 9일 때까지의 모든 경우를 더해준 것이므로 이를 다 더해준다.
더해주면서 mod10007연산을 해주고 최종 결과를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N;
vector<vector<int>> dp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
dp.resize(N + 1, vector<int>(10));
for (int i = 1; i <= N; i++)
{
for (int j = 0; j < 10; j++)
{
if (i != 1 && j != 0) continue;
dp[i][j] = 1;
}
}
for (int i = 2; i <= N; i++)
{
for (int j = 1; j < 10; j++)
{
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 10007;
}
}
int rst = 0;
for (auto a : dp[N])
{
rst += a;
rst %= 10007;
}
cout << rst << '\n';
}
후기
처음에 재귀로 했는데 시간초과가 났다.
1000자리수가들어오면 이를 0부터9까지 10가지를 각 자리마다 해줘야하므로 시간초과가 날거같긴 헀다.
그래서 dp로접근했다.
공식을 유도하는게 빡세긴 했지만 원리를 알면 어찌저찌 구해진다.
