ljy8947   1년 전

조합을 구하는 프로그램을 공부하던 중에 아래와 같은 글을 봤습니다.

f(n,k-1)*(n-k+1)/k 는 오버플로가 발생할 수 있기 때문에 더 안정적인

((n-k+1)/k)*f(n,k-1) 로 쓴다.


일단 첫 번째로, 함수가 앞에 나오는 것과 뒤에 나오는 차이인데, 왜 안정성에 차이가 있는지 알고 싶습니다.

두 번째로 아래의 식과 같이 사용하면, 그리고 괄호를 사용하면 답이 다르게 나옵니다. (예로 10C5 를 구하면 252가 나와야 하는데, 두 번째 식으로 하면 80이 나옵니다.) 이것도 왜 그런지 궁금합니다.

1. f(n, k-1)* (n-k+1)/k = 252 (정답)

2. f(n, k-1)*((n-k+1)/k) = 80 (오답)

3. ((n-k+1)/k) *f(n, k-1) = 80 (오답)

4. (n-k+1)/k *f(n, k-1) = 80 (오답)


세 번째로, 1번과 같은 식을 써서 프로그램을 아래의 소스와 같이 만들었고, 100C6 도 예시와 같이 잘 나오는데 '틀렸습니다'가 나옵니다..

수학적으로 증명한 식인데, 왜 그런건가요 :(

hahaha   1년 전

n-k+1이 k의 배수가 아닐 수 있기 때문에 틀렸습니다가 나옵니다.

또한 우선순위에 따라 계산순서가 달라질 수 있기 때문에, 다른 값이 나오는 겁니다.

곱셈끼리 있을 때는 좌측부터 차례대로, 괄호가 있을 경우 괄호부터 계산되니까요.

이 문제는 보통 파스칼의 삼각형으로 접근합니다.ㅎㅎ

ljy8947   1년 전

hahaha 답변 감사합니다. 함수의 순서와 괄호에 의한 오버플로나 값의 차이는 님의 답변을 보고 이해가 되었습니다! :)


하지만

f(n, k)= n!/(k!*(n-k)!) 이고,

f(n, k-1)= n! / ( (k-1) * (n-k+1) ) 이므로,

f(n, k) = f(n, k-1) * (n-k+1)/(k) 이다.

이 식에 의하면 n-k+1 이 k의 배수가 아닌 것은 상관 없는 것 같아요.. 함수가 풀리면서 값들이 상쇄되어 결국 정수형으로 나옵니다.

예로 주어진 예시를 보면 100 C 6 인데, 100-6+1은 6의 배수가 아님에도 불구하고 답은 예시와 같이 잘 나옵니다.


그리고 아까 올린 소스가 틀렸던 이유는

100 30
-157535421104199204

이라고 값이 오버플로 되더라구요.. 그래서 unsigned long long 으로 바꾸고, 서식 문자는 %llu 로 받아보니

100 30
613292183087190384 라고 나옵니다.

그런데 이상한게

100 50
6883350633527957

라고 나오더라구요..

파스칼의 삼각형을 보면 삼각형의 중심에 있는 값이 가장 커야 되는데, k=50 일 때의 값이 k=30 일 때의 값보다 자릿수가 두 개나 모자라게 나오네요... 왜 이러지..ㅠ


ljy8947   1년 전

아 그리고 시간이 문제가 될 수도 있을 것 같아 소스는 DP를 쓴 거로 고쳤습니다.

hahaha   1년 전

음 .. 해당값이 long long 범위를 넘어가는 문제도 있었네요 ㅠㅠ

빅인티져를 구현하시거나 빅인티저 자료형이 있는 언어를 사용하시는 방법이 있습니다!

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