#5607 조합

[sincheol]

자연수 N과 R이 있고 N combination R의 값을 1234567891로 나눈 나머지 출력

[sincheol]

N은 1000000이하의 양수, R은 N이하, 0이상의 정수 우선 combination계산의 최소화를 위해 N-R이 R보다 작은지 확인 작다면 그 값으로 combination 아니라면 R로 combination

[sincheol]

예상되는 시간복잡도는 combination의 계산에 이용되는 O(n) 정확히 하자면 O(n/2)일 것이다... R을 그대로 combination에 사용하는 것이 아니라 N-R을 통해 절반 이하로 회수를 줄일 수 있어서

[sincheol]

N이 생각보다 커 R이 조금만 커도 정수 표현의 범위를 벗어나서 overflow 발생

[sincheol]

biginteger를 사용해야 할듯 다만 string을 이용해 계산하는 것이라 형변환이 필요

[sincheol]

scanner를 사용해 코드를 작성했는데 주어진 시간내에 문제를 풀지못함. 우선 buffered reader를 사용해 시간을 단축시켜봐야 할듯

[sincheol]

reader를 사용해도 성능의 변화는 없음 그렇다면 combination의 계산수를 줄이는 방법을 생각해야 하는데 알고리즘적으로 줄이는 방법은 없는 것 같아 combination에 대해 찾아봄

[sincheol]

찾아보니 nCr은 n개중에 r개를 순서에 상관없이 뽑는 경우의 수. 이것의 계산을 줄이는 방법은 nCr = n-1Cr-1 + n-1Cr 인 듯. 즉 1개를 지정해 1개를 뽑아서 나머지를 뽑는 경우의수 + 그 1개를 제외하고 나머지에서 모두 뽑는 경우의수를 더한 것

[sincheol]

분명 곱셈연산은 줄어들지만 재귀적으로 호출해서 더하는 것이 성능 향상에 도움이 될지는 모르겠음

[sincheol]

해보니 저것도 의미없음

[sincheol]

페르마의 소정리를 이용해 풀어야함 +처음엔 이것을 왜 사용해야 하는지 몰랐는데 combination의 계산과 모듈러 연산의 과정에서 찾아냄 nCr = n!/(r!(n-r)!) 이다 이것을 모듈러 연산으로 계산하려면

• 위와 같이 계산을 다 끝낸 후 모듈러 연산을 적용해 나머지를 구하는 것과
• 모듈러 연산의 성질에서 곱셈의 분배법칙을 적용해 구하는 법 https://sexycoder.tistory.com/66

나눗셈은 불가능 하기에 n!*(r!(n-r)!)^-1으로 표현한 후 분배법칙을 적용하면 된다. 이때 (r!(n-r)!)^-1로 모듈러 연산을 할 수 없기에 페르마의 소정리에서 모듈러 연산에 대해 합동인 수를 찾아 계산하는 것이다.

[sincheol]

https://m.blog.naver.com/a4gkyum/220768006509 - 페르마의 소정리 이해

1. p가 prime인지 알아야 페르마의 소정리를 정확히 사용가능..(합성수 즉 유사소수라 부르는 것도 페르마의 소정리가 적용될 수도 있지만 p가 prime이면 페르마의 소정리를 쓸 수 있기 때문에 우선)
2. a^p 모양으로 combination의 결과를 어떻게 표현할 것인가 (+필요없음)

[sincheol]

https://devmath.tistory.com/60#:~:text=%EA%B0%80%EC%9E%A5%20%EB%A8%BC%EC%A0%80%20%EC%96%B4%EB%96%A0%ED%95%9C%20%EC%88%98%20X,X%EB%8A%94%20%EC%86%8C%EC%88%98%EA%B0%80%20%EC%95%84%EB%8B%88%EB%8B%A4.

1. 은 우선 rough하게는 2부터 p-1까지의 수를 for문을 돌려 나눠 소수인지 아닌지 판별하는 방법과 약수의 특징을 이용해 p^1/2 값보다 작은 수만으로 위와같이 for문으로 나눠 판별하는 방법 에라토스테네스의 체 방식에서 따와서 첫번째 방법을 줄이는 것도 가능할 듯 다만 메모리를 많이 사용한다는 단점..

[sincheol]

두번째 방법으로 우선 계산해보니 prime number가 맞음 그렇다면 페르마의 소정리를 적용가능

[sincheol]

%연산의 곱셈 분배법칙을 이용해 각 곱셈을 %로 나눠 값을 줄여 계산하는 방법을 생각했었는데 이는 제곱연산 즉 이 문제에서는 O(n*1234567891)... 시간 소비가 너무 큼 제곱연산을 줄이는 방법은 divide and conquer을 사용해 Nlog(1234567891-2)만큼 줄일 수 있다 위 방법에 비해서는 확실히 줄었음