글 읽기 - 수학적으로 맞는데...도저히 어디가 틀렸는지 모르겠어요..

minuk6219 5년 전 0

저의 알고리즘을 설명하자면

숫자 n을 k개의 수를 이용해서 만드는 경우의 수는

n개의 1과 (k-1)개의 막대기를 정렬하는 경우의 수와 같습니다.

따라서 이를 처음에는 팩토리얼로 구하고자 했으나 이는 오버플로우가 나서 다이나믹 프로그래밍을 이용하여 구했습니다.

숫자 n을 k개의 수를 이용하여 만드는 경우의 수는 (n+k-1) ! / ( n! * (k-1)! ) 이고

n을 k+1개의 수를 이용하여 만드는 경우의 수는 (n+k) ! / ( n! * (k)! ) 이므로

d[k+1] = d[k] * (n+k) / k 가 됩니다

이를 식으로 만들어서 풀었는데.. 계속 틀렸습니다가 나옵니다

제가 뭘 놓치는 걸까요 도와주세요

#include<cstdio>

int main(void)
{
	long long n,k;
	long long d[201];
	scanf("%lld %lld",&n,&k);
	d[1] = 1LL;
	for(int j = 2; j <= k ; j++)
		d[j] = ((d[j-1] * (n+j-1))/(j-1)) % 1000000000;
	printf("%lld",d[k]);

	return 0;
}

goo9 5년 전 1

식 자체에는 문제가 없으나 10번라인에서 MOD연산이 실행되면 나누기 연산에서 몫과 나머지가 발생하기 시작할것 같습니다.

좀 더 간단한 연산을 찾아보시는 것도 좋을 것 같네요.

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

문제

문제

출처

ICPC

수학적으로 맞는데...도저히 어디가 틀렸는지 모르겠어요..

minuk6219 5년 전 0

goo9 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말