BOJ 11057 오르막 수

문제출처 : https://www.acmicpc.net/problem/11057

1. 문제요약

- 33455, 012345와 같이 각 자릿수가 오름차순인 수를 오르막 수라 함.

- 인접한 수가 같아도 오름차순으로 인정

- 9111 과 같은 수는 오르막 수가 아님

- 수는 0으로 시작 할 수 있음

- 오르막 수의 갯수는?

- 1 <= n <= 1,000

2. 접근방법

- n자릿수가 1000 이므로 모든 수를 다 확인 할 수 없음

- n 자릿수의 마지막 수가 0 이면, n-1 자릿수의 마지막 수는 0

  n 자릿수의 마지막 수가 1 이면, n-1 자릿수의 마지막 수는 0, 1

  n 자릿수의 마지막 수가 2 이면, n-1 자릿수의 마지막 수는 0, 1, 2

  ...

- 필요한 항목은 자릿수, 마지막 수 이므로

- d[n][j] : n 자릿수, 마지막 수가 j인 오르막 수의 갯수

- d[n][j] = d[n-1][0] + d[n-1][1] + ... + d[n-1][j-1] + d[n-1][j] = ∑(i=0, j) d[n-1][i]

3. 시간복잡도

- n

4. 회고

- 10007의 나머지 이므로 n이 1000 이라 해도 1000자릿수의 10007의 나머지 합이 int 범위를 넘어 갈 수 없음

소스코드

#include<iostream>
using namespace std;

int n, d[1001][10], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			for (int k = 0; k <= j; k++){
				d[i][j] += d[i - 1][k];
			}
			d[i][j] %= 10007;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 10007 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]