[백준문제풀이/정수론 및 조합론] 11051.이항계수 2

문제 내용

전에 풀은 이항계수를 10007로 나눈 나머지를 출력하라.

 

문제 풀이

이게 무슨 개꿀 문제인가! 전에 풀었던 내용에 % 10007 만 붙이면되는거아님?ㅋㅋ 근데 왜이렇게 정답률이 낮지? 했는데...역시나 생각보다 어려운문제다.

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(0);	cin.tie(0);

	int n, k;
	cin >> n >> k;

	int up =  1;
	for (int i = 0; i < k; i++)
	{
		up *= n;
		n--;
	}

	int down = 1;
	int down_k = k;
	for (int i = 0; i < down_k; i++)
	{
		down *= k;
		k--;
	}

	cout << up / down % 10007;

}

런타임 에러, 인티져 오버플로우가 떠버린다. 

인티져 오버플로우는 int 의 값을 벗어났을때 뜨는 오류라고 한다. 즉 , 너무 큰값이 들어간다는 뜻.

 

뭐지.. 그럼 어떻게하지? 이항 계수의 특성이 있나? 미리 값을 나누어서 범위를 넘어설 수 없게 할 수 있나? 했는데

 

두둥! 이럴땐 문제를 천천히 다시 한번 살펴보면 생각 못한 힌트가 나온다.

동적 계획법이요?  ( 동적계획법에 대한 문제도 많이 나오니, 궁금한건 구글에 동적계획법을 검색해보자. )

동적 계획법 문제를 여러개 풀다보면 ,

대충 동적계획법은 데이터들의 규칙을 이용해 그 해당 하는 값을 배열에 저장해두고 그것을 이용해 문제를 더 간단하고 빠르게 풀 수 있는 방법이다.

 

그래서 이 문제는 이제 어떻게 푸느냐?

이항계수의 성질을 또 알아야한다. 어휴!

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이항 계수 - 위키백과, 우리 모두의 백과사전

 

다 볼 필요는 없고,

 

점화식과 이 점화식을 통하면 

n (행 인덱스)

k (열 인덱스) 로 이러한 규칙이 있다는 걸 알 수 있다.

 

즉( n, k) = (n-1)(k) + (n-1)(k-1) 이다.

 

따라서 이러한 풀이가 가능하다.

#include <iostream>
using namespace std;

int dp[1001][1001];

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(0);	cin.tie(0);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n + 1; i++)
	{
		for (int j = 0; j < k + 1; j++)
		{
			if (i == j || j == 0)
				dp[i][j] = 1;
			else
				dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;
		}
	}

	cout << dp[n][k];

}

 

저 파스칼 삼각형의 모양을 가진 알고리즘 문제도 여러번 본 것 같다.

알고 있으면 큰 도움이 될 것 같다.