코드업 3707 합의 개수 : 중복조합 nHr로 푼 문제

www.codeup.kr/problem.php?id=3707

합의 개수

문제 분류 : 보기

문제 설명    내 문제집에 추가

어떠한 정수 n 이 주어지면, n을 만들수 있는 합의 경우의수를 출력한다. ( 자기 자신 하나의 합은 제외 한다.)

입력

정수 n을 입력받는다. ( 2 <= n <= 60)

출력

경우의 수를 첫줄에 출력한다. 수는 같은데 더하는 순서가 다르면 다른 경우로 판단한다.

입력 예시   예시 복사

7

출력 예시

63

 

애초에 문제 해결 방법을 떠올리는데 어려웠다. 

 

하지만 여차여차 확인 

 

m.blog.naver.com/PostView.nhn?blogId=sctivcrmnfe&logNo=220905426953&proxyReferer=https:%2F%2Fwww.google.com%2F 

서로 (같은/다른) 상자에 서로 (같은/다른) 구슬을 넣는 경우의 수

이 사이트 도움 됨 

 

 

위의 문제는 같은 공을 서로 다른 상자에 넣는 방식으로 생각하면 좋다. 즉 kHn-k 

k개의 상자에 n개의 같은 공 넣기 

 

예를 들어 4개라면 4개의 작대기를 2칸, 3칸 4칸의 다른 상자에 넣는 것으로 

2H4-2 + 3H4-3 + 4H4-4 를 구하면 되는 것 

이것이 sum에 더해진다. 

void recv(int n)
{
	unsigned long sum;

	sum = 0; // 안해서 에러 1
	for (int i = 2; i <= n; i++) // 2 3 4
	{
		sum += nHr(i, n - i);
		//cout << nHr(i, n - i) << "  ";
	}
	cout << sum;
}

그래서 위의 식이 나온다.

nHr nCr 함수는 그냥 그 조합 공식 이용해서 품 대신 memorization기법으로 이미 구했던건 저장 

memohh는 필요없을지도? 

 

#include <iostream>
using namespace std;

int memocc[61][61];
int memohh[61][61];

int nCr(int n, int k)
{
	if (memocc[n][k])
		return (memocc[n][k]);
	if (n == 0 || n == 1)
		return (1);
	if (k == 0 || k == n)
		return (1);
	memocc[n][k] = nCr(n-1, k-1) % 10007 + nCr(n-1, k) % 10007;
	//cout << ans << "\n";
	return (memocc[n][k]);
}

int	nHr(int n, int r)
{
	if (memohh[n][r])
		return (memohh[n][r]);
	memohh[n][r] = nCr(n + r - 1, r) % 10007;
	return (memohh[n][r]);
}

void recv(int n)
{
	int sum;

	for (int i = 2; i <= n; i++) // 2 3 4
	{
		sum += nHr(i, n - i);
		//cout << nHr(i, n - i) << "  ";
	}
	cout << sum;
}

int main(void)
{
	int n;
	cin >> n;
	//cout << "b" << nCr(3,2);

	recv(n);
	//cout << memohh[2][2];

}

그래서 이게 나왔는데 틀림 처음에 sum 이 421385? 이렇게 큰 수 나오길래 

%10007 해봤는데 아님 알고보니 sum = 0 초기화 안해줘서 ㅋㅋㅋㅋ

 

#include <iostream>
using namespace std;

int memocc[61][61];
int memohh[61][61];

int nCr(int n, int k)
{
	if (memocc[n][k])
		return (memocc[n][k]);
	if (n == 0 || n == 1)
		return (1);
	if (k == 0 || k == n)
		return (1);
	memocc[n][k] = nCr(n-1, k-1) % 10007 + nCr(n-1, k) % 10007;
	//cout << ans << "\n";
	return (memocc[n][k]);
}

int	nHr(int n, int r)
{
	if (memohh[n][r])
		return (memohh[n][r]);
	memohh[n][r] = nCr(n + r - 1, r) % 10007;
	return (memohh[n][r]);
}

void recv(int n)
{
	int sum;

	sum = 0;
	for (int i = 2; i <= n; i++) // 2 3 4
	{
		sum += nHr(i, n - i);
		//cout << nHr(i, n - i) << "  ";
	}
	cout << sum;
}

int main(void)
{
	int n;
	cin >> n;
	//cout << "b" << nCr(3,2);

	recv(n);
	//cout << memohh[2][2];

}

 

그다음에는 54를 집어넣었을 떄 -1로 오버플로 나서 

unsigned long으로 죄다 바꿔줌 

 

#include <iostream>
using namespace std;

unsigned long memocc[61][61];
unsigned long memohh[61][61];

unsigned long nCr(int n, int k)
{
	if (memocc[n][k])
		return (memocc[n][k]);
	if (n == 0 || n == 1)
		return (1);
	if (k == 0 || k == n)
		return (1);
	memocc[n][k] = nCr(n-1, k-1)+ nCr(n-1, k);
	//cout << ans << "\n";
	return (memocc[n][k]);
}

unsigned long	nHr(int n, int r)
{
	if (memohh[n][r])
		return (memohh[n][r]);
	memohh[n][r] = nCr(n + r - 1, r);
	return (memohh[n][r]);
}

void recv(int n)
{
	unsigned long sum;

	sum = 0; // 안해서 에러 1
	for (int i = 2; i <= n; i++) // 2 3 4
	{
		sum += nHr(i, n - i);
		//cout << nHr(i, n - i) << "  ";
	}
	cout << sum;
}

int main(void)
{
	int n;
	cin >> n;
	//cout << "b" << nCr(3,2);

	recv(n);
	//cout << memohh[2][2];

}

 

➜ g++ 3707nsum.cpp;./a.out

54

-1%

이처럼 처음에 오버플로 났다가

 

➜ g++ 3707nsum.cpp;./a.out

54

9007199254740991%

성공적으로 나온다. :D 

 

성공!