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

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

11057번: 오르막 수

문제

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

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

 

이 문제는 예제에 나와있는거처럼 N이 3일 때까지 노트에 모든 경우의 수를 적어봤더니 식이 보였다.

모든 경우의 수를 적어보며 식을 찾는 건 시간도 오래 걸리고 비효율적이지 몰라도 아직 DP문제에 익숙하지 않고 잘하지 못해서 하는 방법이다. 

 

일단 초기 조건으로 한 자리수일 때는 모두 오르막 수의 개수가 1개로 같다. 그리고 나타낼 때는 2차원 배열을 통해 나타내는데 아래 처럼 나타내었다

d[a][b] => 길이가 a이며 끝자리에 오는 수는 b이다.

 식을 모든 한 페이지에 적어서 보면 대충 규칙이 보이는데

d[2][1] = 11 (1개)

d[2][2] = 12, 22(2개)

d[2][3] = 13, 23, 33(3개)

d[2][4] = 14, 24, 34, 44(4개)

d[i][j] 는 d[i][j-1]의 개수를 모두 포함하며, d[i-1][j]의 개수 또한 포함해야한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#define MAX_SIZE 101
#define swap(type,x,y) do{type t=x; x=y;y=t;} while(0)

using namespace std;

int d[1003][10];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N; int Answer = 10;
	cin >> N;

	for (int i = 0; i <= 9; i++) d[1][i] = 1;
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j <= 9; j++) {
			d[i][j] = (d[i][j - 1] + d[i - 1][j]);
			d[i][j] = d[i][j] % 10007;
			Answer = Answer + d[i][j];
			Answer = Answer % 10007;
		}
	}
	Answer = Answer % 10007;
	cout << Answer << endl; 

	return 0;
}