백준 / 다이나믹 프로그래밍 / 11057번 / 오르막 수 / C++

문제

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

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

10

예제 입력 2 

2

예제 출력 2 

55

예제 입력 3 

3

예제 출력 3 

220

 

#include <iostream>
using namespace std;

const int N = 1e3 + 1;
const int divisor = 1e4 + 7;

int dp[N][10];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	for(int i=0; i<10; i++) {
		dp[0][i] = 1;
	}
	
	for(int i=1; i<=n; i++) {		
		dp[i][0] = 1;
	
		for(int j=1; j<10; j++) {
			dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % divisor;
		}
	}
	
	cout << dp[n][9] << '\n';
		
	return 0;
}

---

일단 dp[i][j] 배열은 자릿수가 i일때 0~j로 끝나는 오르막 수의 갯수를 저장하는 배열이다.

한마디로 dp[i][j]라면 dp[i][0]부터 dp[i][j]까지 의 수를 누적(합)시킨 배열이라고 보면된다

예시로 dp[2][4] 라면 자릿수가 2일때 4로 끝나는 오르막 수의 갯수이다.

따라서 04, 14, 24, 34, 44 총 5개이다.

 

그러면 위를 구하는 알고리즘을 살펴보자.

일단 위와같은 예시인 dp[2][4]를 예시로 들어보자.

일단 dp[2][4]는 적어도 dp[2][3]보다 갯수는 많을 것이다.

dp[2][3]은 3으로 끝나는 두자릿수의 갯수를 의미하는데,

03, 13, 23, 33이 있다.

여기서 끝자리수를 4로 바꿔준다면 04, 14, 24, 34 가 되는데 하나가 빠진것이있다.

바로 44가 빠졌는데 이것은 dp[1][4] 즉, 4로 끝나는 한자리수의 갯수를 가져오면된다.

4에 바로 뒤에 4만 붙여주면 되기 때문이다.

그래서 합치면 dp[2][4]를 구해줄 수 있다.

 

따라서 여기서 우리는 일반항을 구할 수가 있는데, dp[i][j] = dp[i][j-1] + dp[i-1][j]이다.

 

dp[0][i]를 1로 초기화시켜준 이유는 밑의 반복문에서 한자리수를 구할때 계속 1을 더해주기 위함이다.