pmk3745   6달 전

뭐가 잘못 되었을까요..?

shashack   6달 전

오버플로 문제입니다 예를들어

1

1 30

일때 답은 30인데 0이 나옵니다.

divide = 29로 소수죠.. 

잘생각해보시면 22번째 줄 for문을 없애고

13번째 포문 하나로 답을 얻으실 수 있습니다.


힌트를 좀 드리자면 

특히 순열 계산할 때 이와같은 방법을 사용합니다.

어떤 수 i가 있다고 해볼게요.

그러면 이 i는  수열 20, 21, 22, .... , 20+i-1 // 연속된 i개 수

원소들 중에서 한 원소를 배수로 갖습니다. 

이항계수를 구할 때 파스칼의 삼각형을 이용하면 가능한 범위 내에선 오버플로 없이 처리할 수 있습니다.

DP를 섞으면 시간복잡도는 nCr을 구할 때 O(nr)이 됩니다.

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