[👊DP뿌시기 #14] (BOJ 11057) 오르막 수

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

11057번: 오르막 수

문제

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

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

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

입력

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

출력

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

 

---

접근법

지난번에 풀어본 쉬운 계단 수와 비슷한 문제이다.

쉬운 계단 수 문제에선 인접한 계단 수가 1차이 나는 수를 말했다면

오르막 수는 계단 수 상관없이 이전 수와 같거나 커야한다.

 

그래서 해당 문제와 같이

 

DP[i][j] = 길이 i인 수 중 끝이 j인 수

 

로 두고 문제를 풀어보자.

 

 

j=0일 경우, 이전 숫자는 무조건 0이어야한다.

j=1 ~ j=9일 경우, 이전 숫자는 자신과 같거나 작아야 한다.

 

그런데 j=1 ~ j=9를 구할 때, for문을 추가로 사용해서 작은 숫자들을 더할 수 있지만,

DP[i][0] = DP[i-1][0] 일 경우.

DP[i][1] = DP[i][0] + DP[i-1][1] 을 하기만 하면된다.

(DP[i][j-1] 이 DP[i-1][0]부터 DP[i-1][j-1] 까지 포함하므로 DP[i][j] 는 DP[i-1][j]만 더해주면 된다.)

 

이런 식으로하면 이중 for문으로 문제를 해결 할 수 있다.

따라서, 점화식은

i) J=0 DP[i][0] = DP[i-1][0] ii) otherwise DP[i][j] = DP[i][j-1] + DP[i-1][j]

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 1001

using namespace std;

int dp[MAX][10];
int n;

void init() {
	for (int i = 0; i <= 9; i++) {
		dp[1][i] = 1;
	}
}

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

	cin >> n;
	init();

	int tmp = 0;
	for (int i = 2; i <= n; i++) {
		
		for (int j = 0; j <= 9; j++) {

			if (j == 0)
				dp[i][0] = dp[i - 1][0];

			else {
				dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
			}
				
			dp[i][j] %= 10007;
		}
	}

	int res = 0;
	for (int i = 0; i <= 9; i++) {
		res += dp[n][i];
	}
	cout <<res % 10007;
}

 

같이보기

https://parvegoongame.tistory.com/62

[👊DP뿌시기 #4] (BOJ 10844) 쉬운 계단 수