글 읽기 - 시간 초과

gkswns3708 4년 전 0

시간 초과가 떠서 질문드립니다.

재귀 함수 때문에 시간 초과가 난 것으로 생각이 되는데

질문들 보면 nCm = n-1Cm-1+n-1Cm으로 풀었다고

그렇게 풀어도 된다고 하는데

어떤 방법으로 풀어야 하나요?

#include <stdio.h>
int combination(int  n, int r) {
	if(n == r || r == 0) return 1;
	else return combination(n - 1, r - 1) + combination(n - 1, r);
}


int main(){
	//mCn
	int N, n, m, i;
	int num1[30];
	int num2[30];
	scanf("%d",&N);
	for(i = 0 ; i < N; i++){
		scanf(" %d",&num1[i]);
		scanf(" %d",&num2[i]);
	}	
	for(i = 0; i < N; i++){
		printf("%d\n",combination(num2[i],num1[i]));
	}
	return 0;
}

djm03178 4년 전 0

질문에 있는 건 단지 그것만이 아니고, 그것을 메모이제이션해야 한다는 이야기가 분명히 있을 것입니다.

gkswns3708 4년 전 0

제가 초보라 기초적인 코딩 능력밖에 없습니다...

혹시 어떤 부분을 공부해야하거나 어떤 것을 고치면 좋을지 조언 가능할까요?

djm03178 4년 전 0

메모이제이션에 대해 알아보세요.

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

문제

문제

출처

ICPC

시간 초과

gkswns3708 4년 전 0

djm03178 4년 전 0

gkswns3708 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말