[백준] 11057번 오르막 수 C++ 코드

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
ll n,dp[11][1003],res;
// dp테이블은 [마지막 숫자][숫자의 길이]를 의미

ll go(int len, string s) {
	if(len == n) return 1; // 목표 길이에 도달했으므로 1 반환
	ll &ret = dp[s[len - 1] - '0'][len];
	if(ret != 0) return ret;
	// i가 마지막 숫자보다 크거나 같은 경우
	for(int i = 0; i < 10; i++) {
		if(i >= s[len - 1] - '0') {
			ret += go(len + 1, s + to_string(i)) % 10007;
		}
	}
	return ret % 10007;
}

int main() {
	cin >> n;
    // 0부터 9까지 모든 경우를 탐색
	for(int i = 0; i < 10; i++) {
		res += go(1, to_string(i)) % 10007;
	}
	cout << (res % 10007) << '\n';
	return 0;
}

풀이

문제에서 오르막 수는 수의 자리가 오름차순을 이루는 수라고 정의되었다. dp를 이용해서 (n - 1)의 길이에서 끝의 자리가 X일 때의 케이스를 가져와 더 큰 문제를 해결하는 방법을 이용했다.

 

dp테이블의 구성은 dp[마지막 자리 숫자][숫자의 길이]로 이루어져 있다. 그리고 탑 다운 방식으로 해결했다. 만약 길이가 n에 도달하면 1을 반환한다. 그리고 아래에서는 for문을 이용해 0부터 9까지의 숫자를 순회하며 마지막 숫자보다 크거나 같은 경우를 탐색해주었다.