백준 - 오르막 수 (C++)

Pixabay로부터 입수된 Clker-Free-Vector-Images님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 

 이번 문제는 숫자의 길이 N이 주어졌을 때, 길이가 N인 오르막 수의 개수를 구하는 문제이다. 즉, 각 자리의 숫자가 비내림차순이 되어야 한다. 그리고 주의해야할 점이 있다. 문제의 조건에 '수는 0으로 시작할 수 있다.'라는 말이 있다. 즉, N이 4일 때, 0000도 가능하다는 뜻이다. 

 이 문제는 다이나믹 프로그래밍으로 풀 수 있을 것 같다. 그런데 다이나믹 프로그래밍은 무언가를 기록하면서 문제를 풀어나가는데, 무엇을 기록해야 하는지 잘 모르겠다. 그렇기에 N이 1일 때부터 살펴볼 것이다.

우선, N이 1일 때이다. 이 경우는 특별히 고민할 것 없이 총 10개인 것을 알 수 있다.

 

다음은 N이 2일 때이다.

십의 자리가 k일 경우, 일의 자리는 k부터 9까지 가능하다. 이를 통해 N이 2일 때는 답이 55임을 알 수 있다. 하지만 이것으로는 아직 잘 모르겠다.

 

그렇기에 N이 3일 때를 확인해보자.

N이 3일 경우, 모든 경우를 직접 세는 것은 무리일 것 같아 일단은 직접 세지는 않았다. 백의 자리가 0일 경우, 십의 자리가 0부터 9까지가 가능하다. 그리고 이에 따라 일의 자리 숫자도 정해진다. 마찬가지로 백의 자리가 1일 경우, 십의 자리는 1부터 9까지 가능하며 일의 자리 역시 이에 따라 정해진다.

 

위의 이미지를 보니 N이 2일 때의 모습이 보이는 것 같다.

예를 들어, 백의 자리가 0일 경우의 개수는 N이 2이고 십의 자리가 0부터 9까지의 경우의 개수 합이다. 마찬가지로 백의 자리가 1인 경우의 개수는 N이 2이고 십의 자리가 1부터 9까지의 경우 개수 합이다. 이를 통해, 특정 자리의 수가 x일 경우의 총 개수는 뒷 자리의 숫자라 x부터 9까지의 경우의 개수의 합이 된다.

 

 이것을 수식으로 표현해보자. 변수는 자리수와 그 자리수의 숫자 2가지가 존재한다. 그렇기에 다이나믹 프로그래밍의 기록을 위한 배열 dp는 2차원 배열로 표현할 수 있을 것이다.

• dp[a][b]: a 자리의 숫자가 b일 경우의 총 개수
• a는 1부터 N까지의 값을 가진다. 만약 N이 3일 경우, a가 1이라면 일의 자리, 2라면 십의 자리, 3이라면 백의 자리를 의미한다. N이 5라면 a가 1이라면 일의 자리, 5라면 만의 자리를 의미한다.
• b는 a자리의 수가 b일 경우의 총 개수로 0부터 9까지의 수이다.
• 만약 N이 3일 때, dp[1][0]은 백의 자리 수가 0일 경우의 총 개수이다.

dp와 알아낸 사실을 바탕으로 dp[a][b]의 값을 수식으로 나타낸다면, dp[a][b] = dp[a - 1][b] + dp[a - 1][b + 1] + ... + dp[a - 1][9]가 될 것이다. 그리고 N이 3일 때는 이렇게 나타낼 수 있다.

 

이를 코드로 표현하면 다음과 같다.

 

#include <iostream>
#pragma warning(disable:4996)
#define MAX 1001
#define MOD 10007
using namespace std;

int N;
int answer = 0;
int dp[MAX][10];

// digit번째 자리수가 num일 때
int Check(int digit, int num)
{
	if (dp[digit][num] > -1)
		return dp[digit][num];

	int& curDp = dp[digit][num];
	curDp = 0;

	for (int nxtNum = num; nxtNum <= 9; ++nxtNum)
		curDp = (curDp + Check(digit - 1, nxtNum)) % MOD;
	
	return curDp % MOD;
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	cin.tie(0);

	cin >> N;

	for (int digit = 0; digit < MAX; ++digit)
	{
		for (int num = 0; num < 10; ++num)
			dp[digit][num] = -1;
	}

	for (int num = 0; num < 10; ++num)
		dp[1][num] = 1;

	for (int num = 0; num < 10; ++num)
		Check(N, num);

	for (int num = 0; num < 10; ++num)
		answer = (answer + dp[N][num]) % MOD;

	cout << answer << endl;

    return 0;
}