본문 바로가기
Algorithm/Baekjoon

11057_오르막수

by 모너아링 2023. 1. 4.

▶실버1

풀이

처음에는 왜 dp인지 이해가 가지 않음 -> 모든 수를 탐색하며 오르막 수인지 확인하는 작업을 하기엔 시간이 너무 많이 걸리기 때문에 dp로 처리

만약 0_ _이면 한 자리가 추가될 때 0 0 _ _ (1가지) 만 가능

1 _ _이면 0 1 _ _, 1 1 _ _ (2가지) 가능

....

9 _ _이면 0 9 _ _, 1 9 _ _, ~ , 9 9 _ _ (10가지) 가능

이런 식으로 생각하면 자릿수와 맨 앞 자리의 수가 무엇인지를 따져 `dp[i][j] : 맨 앞 자리 수가 j인 i자리의 수의 개수` 로 놓는다.

ex) 3자리 수 오르막 수 구하기

3자리 수의 오르막 수의 개수를 구하기 위해서는 dp[3][0] + dp[3][1] + ... + dp[3][9] 을 구하면 되는데

dp[3][0] = dp[2][0]

dp[3][1] = dp[2][0] + dp[2][1]

...

dp[3][9] = dp[2][0] + dp[2][1] + ... + dp[2][9] 이다.

이런식으로 1자리수부터 n자리수까지의 dp값을 모두 더하면 n자리수의 오르막 수의 개수를 알 수 있다.

이때 기저조건은 dp[1][0 ~ 9] = 1이다.

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[1001][10];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	int sum = 0;
	cin >> n;

	//한 자리 수에는 모두 1
	for (int i = 0; i < 10; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = j; k < 10; k++) {
				dp[i][j] += dp[i - 1][k];
			}
            //dp값이 커질 수 있기 때문에 나머지를 저장
			dp[i][j] %= 10007;
		}
	}
	
	for (int i = 0; i < 10; i++) {
		sum += dp[n][i];
        //문제에서 10007의 나머지가 답이라고 했기 때문에 10007로 나눈 나머지 값이 최종 답
		sum %= 10007;
	}
	cout << sum;
}

'Algorithm > Baekjoon' 카테고리의 다른 글

11660_구간 합 구하기 5  (0) 2023.01.11
11055_가장 큰 증가 부분 수열  (0) 2023.01.10
2003_수들의 합 2  (0) 2023.01.02
21921_블로그  (0) 2023.01.01
2583_영역 구하기  (0) 2022.11.11