[백준] 11570번: 오르막 수

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

11057번: 오르막 수

DP로 풀 수 있는 간단한 문제

1~N자리 오르막수의 끝나는 숫자(0~9)를 배열에 저장해놓고 DP로 풀면 된다. 다만 각 자릿수별로 배열을 몽땅 선언해 버리기가 싫어서 현재 자릿수와 이전 자릿수를 저장하는 동적 배열 curr, prev를 선언했다. 각 자릿수별 계산이 끝날 때마다 curr와 prev를 swap해주면 된다.

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

int main(void) {
	int *prev = new int[10];
	int *curr = new int[10];
	int N;
	int result = 0;

	cin >> N;
	fill(curr, curr + 10, 1);
	fill(prev, prev + 10, 0);

	for (int i = 2; i <= N; i++) {
		swap(prev, curr);
		fill(curr, curr + 10, 0);

		for (int j = 0; j < 10; j++) {
			for (int k = 0; k <= j; k++) {
				curr[j] = (curr[j] + prev[k]) % 10007;
			}
		}
	}

	for (int i = 0; i < 10; i++) result += curr[i];
	cout << result % 10007;
}

그래서 처음 제출했던 답안은 위와 같다.

 

그런데 좀더 생각해보니 굳이 배열을 두개 선언해버릴 필요 없이 하나의 배열로도 가능하겠다 싶었다.

	0	1	2	3	4	5	6	7	8	9
1번째	1	1	1	1	1	1	1	1	1	1
2번째	1	2	3	4	5	6	7	8	9	10
3번째	1	3	6	10	15	21	28	36	45	55

일단 dp[10] 배열을 선언한 뒤, 1로 전부 초기화 시켜놓는다. 그리고 두번째부터는 dp[i] = dp[i] + dp[i-1]이 된다. (정확하게는 10007로 나눈 나머지)

#include <iostream>
using namespace std;

int main(void) {
	int dp[10];
	int N;
	int result = 0;

	cin >> N;
	fill(dp, dp + 10, 1);

	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < 10; j++) {
			dp[j] = (dp[j] + dp[j - 1]) % 10007;
		}
	}

	for (int i = 0; i < 10; i++) result += dp[i];
	cout << result % 10007;
}

그렇게 나온 최종 답안!