[Silver I] 오르막 수 - 11057

문제 링크

성능 요약

메모리: 2060 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2026년 2월 7일 20:11:00

문제 설명

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

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

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

입력

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

출력

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

첫 제출코드

접근 및 첫 제출코드

// 11057
// 
// - 아이디어
// 점화식 -> dp[n][마지막숫자] = dp[n-1][가능한숫자 전부]
// ex) dp[n][9] = dp[n-1][9] ... dp[n-1][0];
// ex) dp[n][8] = dp[n-1][8] ... dp[n-1][0];
// 
// - 복잡도
// O(n)? <- 가능
// n*10^2 => 약 10^5
// 
// - 자료구조
// int[][] : dp

#include <bits/stdc++.h>

constexpr int MODULER = 10'007;
int dp[1001][10];

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N;
	std::cin >> N;

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

	// solve
	for (int n = 2; n <= N; n++) {
		for (int m = 0; m <= 9; m++) {
			for (int i = 0; i <= m; i++) {
				dp[n][m] = (dp[n][m] + dp[n - 1][i]) % MODULER;
			}
		}
	}

	// answer
	int answer = 0;
	for (int i = 0; i <= 9; i++) {
		answer = (answer + dp[N][i]) % MODULER;
	}
	std::cout << answer;

	return 0;
}

첫번째 방법

점화식 -> dp[n][마지막숫자] = dp[n-1][가능한숫자 전부] ex) dp[n][9] = dp[n-1][9] ... dp[n-1][0]; ex) dp[n][8] = dp[n-1][8] ... dp[n-1][0];

	for (int n = 2; n <= N; n++) {
		for (int m = 0; m <= 9; m++) {
			for (int i = 0; i <= m; i++) {
				dp[n][m] = (dp[n][m] + dp[n - 1][i]) % MODULER;
			}
		}
	}

dp[n][m]을 구할때마다 이전행의 0~m까지 값을 다 더하여 계산했다 -> dp[n-1][0~m]

자아 성찰

3중 루프문이지만 복잡도는 n<=1000인 상황에서 10^5이기 때문에 문제는 없으나,,

사실 0~m까지 다 더할 필요가 없다. dp[n - 1][0~m]과 같은 값을 얻기 위해 dp값 두개만 읽어도 된다.

바로 dp[n][m] = dp[n-1][m] + dp[n][m-1] 이다.

기존의 값에서 dp[n-1][m]만 더하고, 나머지 dp[n-1][0 ~ m-1]의 합계가 ===> dp[n][m-1]과 동일하기 때문이다..

실제 값으로 얘기하자면,, 나는 dp[3][4]의 값을 얻으려고 할때 매번 dp[2][0~4]의 값을 다 더했다. 이때 이전에 똑같은 원리로 dp[3][3] 에는 [2][0~3] 의 값이 존재한다. 그렇다면 굳이 0~4를 더 할 필요없이 dp[3][3]의 값과 나머지 dp[2][4]의 값 두 개만 더 해주면 된다!

따라서 **dp[n][m]은 dp[n-1][m]값과 0~m-1의 값을 가진 dp[n][m-1]의 값을 더하면 되겠다.

개선한 최종 코드

// 11057
// 
// - 아이디어
// 점화식 -> dp[n][마지막숫자] = dp[n-1][가능한숫자 전부]
// ex) dp[n][9] = dp[n-1][9] ... dp[n-1][0];
// ex) dp[n][8] = dp[n-1][8] ... dp[n-1][0];
// 
// - 자료구조
// int[][] : dp

#include <bits/stdc++.h>

constexpr int MODULER = 10'007;
int dp[1001][10];

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N;
	std::cin >> N;

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

	// solve
	for (int n = 2; n <= N; n++) {
		for (int m = 1; m <= 9; m++) {
			dp[n][m] = (dp[n-1][m] + dp[n][m-1]) % MODULER;
		}
	}

	// answer
	int answer = 0;
	for (int i = 0; i <= 9; i++) {
		answer = (answer + dp[N][i]) % MODULER;
	}
	std::cout << answer;

	return 0;
}