#11057: 오르막 수

백준 11057번: 오르막 수

문제:

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

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

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

입력:

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

풀이:

• 이 문제는 2차원 배열(dp[길이][끝에 자리수])를 생성하여 끝에 자리에 따라 경우의 수를 따로 저장 한 뒤 마지막에 모든 값들을 더 해주는 방식으로 풀었다. 바텀업 방식으로 1부터 n까지 값들을 차근 차근 저장하면서 이전 값을 이용해 배열을 채워 나가면 된다.

• 우선, base case인 길이가 1인 경우에 모든 끝자리마다 경우의 수가 1이기 때문에 1로 초기화 해준다. 다음으로 배열의 길이 2부터 n까지 값을 올리면서 모든 길이의 경우의 수를 적을 것이다. 해당 길이의 모든 끝에 자리수(0~9)의 경우의 수를 계산 해준다. 끝에 자리의 경우의 수는 이전 길이의 경우의 수 중에 끝에 자리가 자신보다 작거나 같은 경우만 더해주면 된다. 예를 들면, 현재 길이가 2이며 끝에 자리가 2인 경우면 오르막 수를 만들기 위해서는 이전 숫자가 0, 1, 2이면 되기 때문에 이전 길이의 0, 1, 2인 경우를 더해주면 현재 길이가 2인 경우의 수가 나온다.

  ⚠️ 배열의 합을 구할 때 마다 문제에서 출력 조건으로 제시한 %10007을 해주는 것을 잊지 말자. 또한, += 연산을 사용하면 % 연산의 효과가 없는 것을 유의하자.

• 마지막으로 길이 n의 모든 끝에 자리 값의 경우의 수를 합해준 뒤(합할 때도 %10007을 해주어야 된다) 정답을 출력 해준다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, answer=0, dp[1001][10]={};
	//입력
	cin >> n;
	//길이가 1인 경우 배열 초기화
	for(int i = 0; i < 10; i++) dp[1][i] = 1;
	//길이가 2인 경우부터 n인 경우까지 바텀업 방식으로 계산
	for(int i = 2; i <=n; i++){
		//j는 끝에 자리수를 의미
		for(int j = 0; j < 10; j++){
			//끝에 자리수(j)보다 작거나 같은 값들을 끝자리 인덱스로 갖고 있는 값들의 경우의 수를 모두 합한다
			for(int k = 0; k <= j; k++) dp[i][j]=(dp[i][j]+dp[i-1][k])%10007;
		}
	}
	//끝에 자리수의 경우의 수를 모두합한다
	for(int i = 0; i < 10; i++) answer= (answer+dp[n][i])%10007;
	//출력
	cout << answer;
}