백준 11057번: 오르막 수

[문제 링크]

11057번: 오르막 수

---

간단한 dp 문제였다.

 

시작 숫자와 자릿수를 상태값으로 가져야하기 때문에 2차원 dp 배열이 필요하다.

 

문제 조건을 보면 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 인정해준다고 되어있기 때문에 이를 유의하여 점화식을 세워주면 된다.

 

top-down 방식의 경우 시작 숫자가 i 일 때 그 뒤에 나올 수 있는 숫자는 i보다 같거나 큰 숫자이다. 따라서 시작 숫자를 i로 하고 자릿수-1을 매개변수로 넘겨주어 재귀호출하는 방법으로 풀 수 있다. 첫번째 자리에 올 수 있는 숫자는 0~9이므로 이를 다 더해주면 된다. 기저사례로 자릿수가 0일 때 끝에 도달했으므로 1을 반환한다.

 

bottom-up 방식의 경우 자리수가 1이고 시작 숫자가 0~9 일 때 가질 수 있는 경우의 수를 미리 저장한 다음, 임의의 수 i부터 시작하고 자리수가 N인 경우의 수는 시작 숫자가 i~9이고 자리수가 N-1인 경우의 수의 합인 것을 이용하여 값을 갱신해가면 간단하게 원하는 결과를 얻을 수 있다. 

---

#include <iostream>
#include <cstring>
using namespace std;

int memo[10][1001];

int Topdown(int start, int N)
{
	if (N == 0) return 1;

	int& ret = memo[start][N];
	if (ret != 0) return ret;

	for (int i = start; i < 10; i++)
		ret += Topdown(i, N - 1) % 10007;

	return ret % 10007;
}

int Bottomup(int N)
{
	memset(memo, 0, sizeof(memo));

	for (int i = 0; i < 10; i++)
		memo[i][1] = 10 - i;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j < 10; j++)
			for (int k = j; k < 10; k++)
				memo[j][i] += (memo[k][i - 1] % 10007);

	return memo[0][N] % 10007;
}

int main(void)
{
	int N;
	cin >> N;

	// top-down
	cout << "top-down: " << Topdown(0,N) << endl;

	// bottom-up
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 75 day