BaekJoon 11057 오르막수

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

소스결과 2024 KB 0 ms

출처 BackJoon 

언어 C++17

분류 다이나믹 프로그래밍

 

설명

1234, 55557 과 같이 모든 자리의 수가 다음 자리 수보다 같거나 큰 수인 경우의 수를 헤아리는 방법

최대 입력이 1000 이고 개수를 10007로 나눈 나머지를 구해 한다.

 

long long int로 최대 크기까지 늘려도 정답은 오답으로 나온다.

어짜피 10007로 나누어야 한다는 조건이기에 모든 경우의 수에서 10007로 나눈 나머지를 dp의 값으로 사용 해도 된다.

% 연산자의 특성상 ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c이기 떄문에

합을 구하고 % 연산자를 넣어주어야 한다.

 

1 ~ 3 까지의 경우를 보면

 

	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	10	9	8	7	6	5	4	3	2	1
3	55	45	36	28	21	15	10	6	3	1

 

 

 

0 - 9 순서보다 9 - 0 순서로 하는게 점화식을 세우기 쉽다.

 

알고리즘

1. DP table을 초기화 한다.

2. DP table[n] 의 총합을 10007로 나눈 나머지를 구해 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000;
const int DIGIT_MAX = 10;
int dp[MAX][DIGIT_MAX];

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < DIGIT_MAX; i++)
		dp[0][i] = 1;

	//DP Table Init
	for (int i = 1; i < MAX; i++)
	{
		for (int j = 0; j < DIGIT_MAX; j++)
		{
			if (j)
			{
				dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
				dp[i][j] %= 10007;
			}
			else
				dp[i][j] = 1;
		}
	}

	int sum = 0;
	for (int i = 0; i < DIGIT_MAX; i++)
		sum += dp[n - 1][i];

	cout << sum % 10007 << endl;

	return 0;
}