(1) 실수 오차
(2) 중간 중간에 일어날 수 있는 오버플로우 문제
그런데 사실 (2)로 인해 틀리시진 않으셨을 거고요.
(1) 이 꽤 커보이네요. 예를 들어봅시다. m = 30, n = 15라고 하면..
일단 이렇게 계산이 될 거에요.
30/1 * 29/2 * 28/3 * 27/4 * ...
문제는요. double형으로 28/3을 정확하게 표현하지 못합니다. 약간의 오차가 생깁니다.
그게 누적되었기 때문에 꽤 큰 오차가 생긴 것이지요.
1010번 - 다리 놓기
(1) 실수 오차
(2) 중간 중간에 일어날 수 있는 오버플로우 문제
그런데 사실 (2)로 인해 틀리시진 않으셨을 거고요.
(1) 이 꽤 커보이네요. 예를 들어봅시다. m = 30, n = 15라고 하면..
일단 이렇게 계산이 될 거에요.
30/1 * 29/2 * 28/3 * 27/4 * ...
문제는요. double형으로 28/3을 정확하게 표현하지 못합니다. 약간의 오차가 생깁니다.
그게 누적되었기 때문에 꽤 큰 오차가 생긴 것이지요.
그러면 이걸 어떻게 풀 수 있을까요? m, n이 적당히 작은 경우
2차원 배열을 선언해서 푸실 수 있습니다. 흔히 아시는. nCm = n-1Cm + n-1Cm-1 을 이용해서 푸실 수 있고요. 이 때는
O(n^2) 정도 됩니다.
그게 힘든 경우 에라스토스의 체 + 소인수 분해를 해서 푸실 수 있습니다. 이게 가장 쉬운 방법이고요.
이 때 시간복잡도는 O(n^2)보다는 작습니다.
(1) 일단 1부터 n까지 에라스토스의 체를 이용해서 소수를 걸러내는 것 : O(nlog(logn))
(2) n보다 작은 소수는 대충 n/logn개
(3) a*(a+1)*...*(b-1)*b에 소수 x가 몇 개 있는가? 이건 대충 O(log(x))
복잡도는 (2) + (3)에 의해서 결정될 거 같네요.
진짜로 계산하고 싶으시다면 여기 참고하세요.
https://en.wikipedia.org/wiki/...
약간 도움이 될 지도 모르겠습니다.
저 방식으로 풀려면..
소인수 분해를 하셔야 합니다.
네. 그런데. 이건 n, m이 크지 않으므로
dp로 푸는 게 제일 빠르고 쉬운 방법일 거에요.
댓글을 작성하려면 로그인해야 합니다.
zzong0324 4년 전
예제도 실수 오차범위 초과하지 않고 잘 출력 되는데 왜 틀리는지 모르겠습니다..