[알고리즘] 백준 11057번: 오르막 수 (C++)

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

11057번: 오르막 수

0 이후에는 0~9 사이의 수

1 이후에는 1~9 사이의 수

...

이와 같은 규칙이 존재하는 것을 알고 2차원 배열을 선언하여

cache[n번째 자릿 수][0~9사이의 수]로 선언하고, [n - 1번째 자릿수]가 [0~9사이의 수 중 하나]일 때 몇 가지 수가 나올 수 있는지 계산해주면 된다.

 

[점화식]

(n != 1 && n != 2)일 때 다음을 만족한다.

for (int k = 9; k >= j; k--) {
	cache[n][j] += cache[n - 1][k];
}

 

[MOD의 위치]

아무 생각 없이 10007을 나눈 나머지 값을 넣다가 오답이 떴다.

for (int i = 3; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 9; k >= j; k--) {
				cache[i][j] += cache[i - 1][k] % MOD;
			}
		}
	}

이 위치에 넣어도 나머지 정리( (a + b)modN = (amodN + bmodN) modN )로 인해 맞는 말이지만

제일 안 박스에 있는 for문을 끝내고도 나머지 연산을 해줘야 한다.

 

for (int i = 3; i <= n; i++) {
	for (int j = 0; j <= 9; j++) {
		for (int k = 9; k >= j; k--) {
			cache[i][j] += cache[i - 1][k] % MOD;
		}
		cache[i][j] %= MOD;
	}
}

 

[AC 코드]

#include <iostream>
#define MAX 1000 + 1
#define MOD 10007
using namespace std;

int n;
int cache[MAX][10];

int main() {
	cin >> n;

	// 초기화
	for (int i = 0; i < 10; i++) {
		cache[1][i] = 1;
	}

	for (int i = 0; i < 10; i++) {
		cache[2][i] = 10 - i;
	}

	for (int i = 3; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 9; k >= j; k--) {
				cache[i][j] += cache[i - 1][k] % MOD;
			}
			cache[i][j] %= MOD;
		}
	}

	int result = 0;
	for (int i = 0; i <= 9; i++) {
		result += cache[n][i];
	}

	cout << result % MOD;
	return 0;
}