글 읽기 - 이항쇼다운 런타입에러 질문입니다

haeran97 5년 전 0

안녕하세요. 문제에 나온 테스트케이스는 되고, 전에 조합문제도 똑같이 풀었는데 이항쇼다운은 런타임에러 뜨네요.

1000000 1<- 로 할때, 38번째 줄에서 스택오버플로우에러가 뜬다네요.

데이터값이 워낙 커서 BigInteger 사용한건데 하도 재귀함수 돌리니까 무한히 반복된다고 멈춘걸까요?

코드에관한 조언은 다 듣겠습니다! 다시 짜라고 하셔도 돼요. 고수님들 부탁드립니다 ㅠ.ㅜ..

import java.io.IOException;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		while(true) {
			Scanner sc=new Scanner(System.in);
			long n=sc.nextInt();
			long k=sc.nextInt();
			
			if(n==0&&k==0) break;
			long nK=n-k; //n-k!
			
			BigInteger arg[]=new BigInteger[(int)n+1];//팩토리얼을 담는 배열
			
			BigInteger binomialCoef=BigInteger.ONE;
			BigInteger n1=factorial(n,arg);
			BigInteger nK1=factorial(nK,arg);
			BigInteger k1=factorial(k,arg);
			
	
			binomialCoef=n1.divide(k1.multiply(nK1));
			System.out.println(binomialCoef);
		}

	}
	public static BigInteger factorial(long n,BigInteger[] arg) {//재귀함수로 만들어놓고-> 메모이제이션
		if(n==0) return BigInteger.valueOf(1);
		else {
			if(arg[(int)n]==null)//계산한적 없으면
			{
				if(arg[(int)n-1]!=null)
					arg[(int)n]=arg[(int)n-1].multiply(BigInteger.valueOf(n));
				else//전에fac이 없으믄
					arg[(int)n]=factorial(n-1,arg).multiply(BigInteger.valueOf(n));
			}
		}
		return arg[(int)n];
	}

}

alice 5년 전 1

n값이 워낙 크기 때문에 메모이제이션이 아닌 다른 방법으로 푸시는 걸 추천드립니다.

이 문제를 해결할 때 생각해야 하는 부분은 크게 두 가지 입니다.

1. 계산 과정에서 오버플로우가 발생해 결과값이 제대로 나오지 않을 수 있다는 점

2. 불필요한 연산을 다시 수행시키지 않도록 해야 한다는 점

조합의 특성을 생각해보시면 위의 문제들을 해결할 수 있습니다.

haeran97 5년 전 0

조언 감사드립니다! 조합에 대해 좀 더 공부하고 다시 풀어볼게요

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

문제

문제

출처

ICPC

이항쇼다운 런타입에러 질문입니다

haeran97 5년 전 0

alice 5년 전 1

haeran97 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말