글 읽기 - 예제 세개중....(쉬운 질문!!)

dong149 8년 전 1

예제 세개중에 13 29가 0으로 계산되네요.... 정수값이 너무커서 그런 것 같은데 해결방법좀 부탁드립니다. ㅠㅠ

#include <stdio.h>
#include <stdlib.h>

int factorial(int n)
{
	if(n <= 1)
		return 1;
	return factorial(n-1) * n;
}

int main()
{
	int i;
	int t;
	int *n;
	int *m;
	int *result;
	scanf("%d",&t);
	//t개 진행해야한다.
	n = (int*)malloc(sizeof(int)*t);
	m = (int*)malloc(sizeof(int)*t);
	result = (int*)malloc(sizeof(int)*t);
	
	for(i=0;i<t;i++)
	{
		scanf("%d %d",&n[i],&m[i]);
		result[i] = (factorial(m[i])/factorial(n[i]))/factorial(m[i]-n[i]);
		
	}
	for(i=0;i<t;i++)
	{
		printf("%d\n",result[i]);
	}
	free(n);
	free(m);
	free(result);
	return 0;
}

20151571 8년 전 1

29!는 정수형 뿐만 아니라 long long 에서도 오버 플로우가 나는 엄청나게 큰 숫자라서

29!를 구해주기 보다는

반복문으로 m부터 n 까지 곱해주면서 동시에 1부터 n 까지(맞나??) 나눠 주는 방식으로 하시면 됩니다!!

portableangel 8년 전 1

nCr = n-1Cr-1 + n-1Cr

위 공식을 이용해 계산하면 오버플로 없이 int 범위 내에서 29C13의 값을 계산할 수 있습니다.

dong149 8년 전 0

감사합니다!!!

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

문제

문제

출처

ICPC

예제 세개중....(쉬운 질문!!)

dong149 8년 전 1

20151571 8년 전 1

portableangel 8년 전 1

dong149 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말