프로젝트 오일러 053
nCr이 백만을 넘는 경우 세기
문제
사이냅소프트
순열이나 조합의 계산은 팩토리얼의 분수 형식이기 때문에 아주 큰 수와 아주 큰 수의 나눗셈이 됩니다. 하지만 우리는 어린 시절에 이와 관련된 문제를 풀어보았고, 수십 자리 숫자의 곱셈이나 나눗셈을 해야할만큼 그 문제들이 가혹하지 않았다는 것도 알고 있습니다.
그냥 풀기
조합의 공식이 있기 때문에, 사실 그냥 큰 수로 계산하면 됩니다. 팩토리얼을 계산하는 함수만 있으면요. 그리고 nCr은 "n개 중에서 r개를 선택하는 조합의 수"를 말하기 때문에 항상 n >= r 입니다.
from functools import reduce
prod = lambda xs: reduce(lambda x, y: x * y, xs)
factorial = lambda n: 1 if n < 2 else prod(range(1, n + 1))
def nCr(n: int, r: int) -> int:
return reduce(lambda x, y: x // y, map(factorial, (n, r, n - r)))
def main():
res = 0
for n in range(1, 101):
for r in range(1, n + 1):
if nCr(n, r) >= 100_0000:
res += 1
print(res)
if __name__ == "__main__":
main()약분
팩토리얼의 결과는 큰 수가 나오는 경우가 많지만, 많은 경우 nCr의 결과는 또 그렇게 크지 않은 경우도 많습니다. 그리고 흥미로운 것 중 하나는, nCr의 결과는 나눗셈 연산의 결과이지만, 늘 자연수가 나옵니다. 즉 그 분수식의 분모가 모두 약분이 된다는 뜻입니다. 인수끼리 약분하여 계산해야 하는 양을 줄이는 것도 큰 수의 계산을 피할 수 있는 방법 중 하나입니다. 물론 nCr(1024, 2) 와 같은 계산은 여전히 너무나 큰 수가 되겠지만요.
어쨌거나 분모의 각 인자들이 1이 될 때까지 약분 가능한 분모의 인자들과 약분하면 분모의 인자만 남게 되어 최종적으로 계산해야 하는 양이 줄어듭니다 물론 이를 위해서는 루프를 돌면서 성능의 희생은 불가피합니다.
from functools import reduce
def gcd(a, b):
if b > a:
return gcd(b, a)
r = a % b
if r == 0:
return b
return gcd(b, r)
def nCr(n, r):
ns = list(range(1, n + 1))
rs = [*range(1, r + 1), *range(1, n - r + 1)]
for k in range(len(rs)):
for j in range(len(ns)):
if rs[k] == 1:
break
g = gcd(ns[j], rs[k])
if g > 1:
ns[j], rs[k] = ns[j] // g, rs[k] // g
return reduce(lambda x, y: x * y, ns)
def main():
return sum(
nCr(n, r) > 100_0000 for n in range(1, 101) for r in range(1, n + 1)
)
if __name__ == "__main__":
print(main())이항정리
nCr의 원리에 대해서 조금 더 깊이 생각해보겠습니다. n개 중에서 r개의 요소를 고르는 방법입니다. 이를 각각의 요소에 대한 관점에서 접근해보면 다음과 같이 생각해볼 수 있습니다.
- 먼저 어떤 특정한 원소 1개에 대해서 우리가 고를 수 있는 선택지는 그 원소를 선택하거나, 선택하지 않거나 둘 중 하나입니다.
- 만약 그 원소를 선택했다면, 남은 선택의 조합은 (n - 1)개 중에서 (r - 1)개를 선택하는 방법의 수와 같습니다.
- 만약 그 원소를 선택하지 않는다면, 남은 선택의 조합은 (n - 1)개 중에서 r개를 선택하는 방법의 수와 같습니다.
- 특정한 원소의 선택에 대해서는 그 원소를 선택하거나, 선택하지 않거나의 둘 중 하나의 사건만 일어날 수 있습니다. 따라서 n개 중에서 r개의 원소를 고르는 조합의 수는 2와 3의 합과 같습니다.
이를 식으로 쓰면 nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r) 이 됩니다. 점화식의 모양을 하고 있고, nCr(n, 1) = n이고, nCr(n, n) = 1 인 점을 생각하면 조합의 수는 점화식을 통해서 계산할 수 있고, 기저 케이스에 대한 값이 있으니 재귀나 동적 계획법을 사용해서 구현이 가능합니다.
from functools import wraps
def memoize(f):
memo = {}
@wraps(f)
def inner(*x):
if x in memo:
return memo[x]
r = f(*x)
memo[x] = r
return r
return inner
@memoize
def nCr(n, r):
if r == 1:
return n
if n == r:
return 1
return nCr(n - 1, r) + nCr(n - 1, r - 1)
def main():
return sum(nCr(n, r) > 100_0000
for n in range(1, 101) for r in range(1, n + 1)
)
if __name__ == '__main__':
print(main())
동적계획법으로 구현하기
s = [0] * 10000
s[::100] = [i + 1 for i in range(100)] # nCr(n, 1)
s[::101] = [1] * 100 # nCr(m, m)
for n in ragne(1, 100):
for r in range(1, n):
s[n*100 + r] = min(100_0001, s[n*100+r-100] + s[n*100+r-101]
print(sum(x > 100_0000 for x in s))
