[백준 11057 : C++] 오르막 수 / DP

풀이

---

오르막 수는 수의 자리가 오름차순을 이루는 수. (인접한 수가 같아도 오름차순으로 친다.)

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램. (수는 0부터 시작)

DP 문제는 메모이제이션을 어떤 식으로 둬야할지에 대한 아이디어가 굉장히 중요한 거 같다.

이 문제에서는 메모이제이션을 D[i][j] // i: 수의 길이, j: 마지막 수 로 뒀다는게 중요한 포인트다.

 

 

 

 

코드

---

C++ 언어를 이용해 코드로 살펴보자.

#include <iostream>
using namespace std;
 
constexpr int mod = 10007;
 
int N, ans;
long long D[1001][10]; // D[i][j] = 수의 길이가 i이며 마지막 숫자가 j인 수의 오르막 수의 개수 
 
int main() {
	cin >> N;
	for (int i = 0; i < 10; i++) D[1][i] = 1; // 길이가 1인 숫자들의 오르막 수 초기화
	
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k <= j; k++) {
				// 길이가 i, 마지막 숫자가 j인 수의 오르막 수의 개수는 
				// 길이가 i-1이고 마지막 숫자가 j 이하인 오르막 수의 개수들의 모든 합으로 표현할 수 있다.
				D[i][j] += D[i - 1][k];
				D[i][j] %= mod;
			}
		}
	}
	for (int i = 0; i < 10; i++) ans += D[N][i];
	cout << ans % mod << "\n";
	return 0;
}