[BOJ] 11057 오르막수

Link

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

Note

1234, 55557 과 같이 모든 자리의 수가 다음 자리 수보다 같거나 큰 수인 경우의 수를 헤아리는 방법
최대 입력이 1000 이고 개수를 10007로 나눈 나머지를 구해 한다.

long long int로 최대 크기까지 늘려도 정답은 오답으로 나온다.
어짜피 10007로 나누어야 한다는 조건이기에 모든 경우의 수에서 10007로 나눈 나머지를 dp의 값으로 사용 해도 된다.
% 연산자의 특성상 ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c이기 떄문에
합을 구하고 % 연산자를 넣어주어야 한다.

알고리즘

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;
}

2019-01-12 14:00:00에 Tistory에서 작성되었습니다.