글 읽기 - 제 아이디어에 무슨 문제가 있을까요..?

furyhunter 6년 전 0

사이트 N과 M이 주어진다고 할 때, 각 점을 N0, N1, N2, ..., M0, M1, M2, ... 라고 한다면

N0가 M0에 고정될 때 경우의 수는 M - 1개 중에 N - 1개를 고르는 경우의 수,

N0가 M1에 고정된다면 M - 2개 중에 N - 1개를 고르는 경우의 수..

하는 식이기에 모든 경우의 수는

(M - 1) C (N - 1) + (M - 2) C (N - 1) + ... (좌우가 같아질 때)

까지의 합이 된다고 생각해서 코드를 짜봤습니다.

그 결과 이것저것 테스트해봤는데 작은 숫자들은 잘 나오는 것 같았습니다.

근데 예제에서 13 29는 67863915가 아니라 67863911이 나오더라구요..

혹시 제 아이디어나 코드에서 문제가 있을까요..?

#include <iostream>
#include <math.h>

using namespace std;

//숫자 N과 M의 사이트가 있음.
//두 점을 연결해서 다리를 놓으려고 하는데 한 사이트는 한 사이트에 연결되고, 겹쳐질 수 없음.
//다리를 최대한 많이 놓을 수 있는 경우의 수를 출력

//3 X 4라고 하면, 
//N0, M0를 연결하면 그 경우의 수는 2 X 3과 같음.
//N0, M1을 연결하면 2 X 2와 같음.
//N0, M2를 연결하면 2 X 1과 같음.

//N1, M0를 연결하면 1 X 3과 같음.
//N1, M1을 연결하면 1 X 2
//N1, M2 : 1 X 1

//근데 최대로 연결하길 원하니까 N0를 시작점으로 하는 것만 생각하면 됨.

//N0, M0 : 2 X 3 -> 3C2 = 3
//N0, M1 : 2 X 2 -> 2C2 = 1

//(M - 1)C(N - 1) + (M - 2)C(N - 1) + ...
//M - n == N - 1이 될때까지

long long comb(int n, int r)
{
	double result = 1;
	int t = r;

	for (int i = n - r + 1; i <= n; i++)
	{
		result = result * (double)i / (double)t;

		t--;
	}

	return result;
}

int main()
{
	int N, M;
	long long sum = 0;

	cin >> N >> M;

	if (N == 1)
		sum = M;
	else
	{
		for (int i = M - 1; i >= N - 1; i--)
		{
			//cout << i << " " << N - 1 << " : " << comb(i, N - 1) << "\n";
			sum += comb(i, N - 1);
		}
	}

	cout << sum << "\n";

	return 0;
}

furyhunter 6년 전 0

조언 감사드립니다!

코드를 아래와 같이 고쳐서 예제 13 29 에 대해서는 제대로 출력이 됩니다.

그런데 제출해보니 50%에서 틀렸다고 나오네요..

혹시 다른 문제가 있을까요..?

#include <iostream>
#include <math.h>

using namespace std;

//long long으로 반환하던걸 double로 바꿈.
double comb(int n, int r)
{
	double result = 1;
	int t = r;

	for (int i = n - r + 1; i <= n; i++)
	{
		result = result * (double)i / (double)t;

		t--;
	}

	return result;
}

int main()
{
	int T;
	int N, M;

	cin >> T;

	while (T > 0)
	{
		double sum = 0;

		cin >> N >> M;

		if (N == 1)
			sum = M;
		else
		{
			for (int i = M - 1; i >= N - 1; i--)
				sum += comb(i, N - 1);
		}

        //double로 받아서 출력할때 캐스팅
		cout << (long long)(sum) << "\n";

		T--;
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 아이디어에 무슨 문제가 있을까요..?

furyhunter 6년 전 0

furyhunter 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말