Project Euler

프로젝트 오일러 015

프로젝트 오일러 15번, 20x20 격자의 좌상단에서 우하단으로 가는 경로의 수를 구합니다. 이는 40번의 이동 중 20번의 아래쪽 이동을 선택하는 조합 문제와 같으며, 40! / (20! * 20!) 공식을 이용한 풀이를 제시합니다.

1분
#project euler #python

시각적으로 표시되는 경로를 문자열과 같은 다른 방법으로 축약해서 표현해봅시다. 오른쪽으로 진행하는 것을 a, 아래쪽으로 진행해야 하는 것을 b라고 한다면 2×2 격자에서의 모든 경로는 다음과 같이 문자열로 표현할 수 있습니다.

  • aabb
  • abab
  • abba
  • baab
  • baba
  • bbaa

이것은 [‘a’, ‘a’, ‘b’, ‘b’]에서 순열을 만는 것과 같습니다. 다만 같은 a끼리, 같은 b끼리는 구분할 수 없으므로 중복을 제외해야 하지요. 따라서 로 계산할 수 있습니다. 격자가 아주 커져서 20×20인 경우에도 숫자만 커진 동일한 문제입니다. 을 계산하면 됩니다.

def factorial(n: int) -> int:
  s = 1
  if n > 1:
    for i in range(2, n + 1):
      s *= i
  return s

factorial(40) // factorial(20) // factorial(20)

약분하여 계산하기

큰 정수를 사용하지 않고 싶다면, 실제로 곱셉과 나눗셈 식을 쓰고 약분 가능한 수들을 약분한 후에 남은 분자의 숫자들만 곱하여 계산하는 방법도 있습니다. 최종 결과는 (40 × 39 × … × 21) ÷ (20 × 19 × … × 2 × 1) 입니다. 따라서 분자와 분모에 들어갈 수들을 리스트로 만들고 약분 가능한 조합을 찾아 약분하고, 분자의 값만 곱할 수도 있습니다. 큰 정수를 지원하지 않는 언어에서는 이런 방식을 사용할 수 있겠죠.

A = list(range(1, 21))
B = list(range(21, 41))

for i in range(20):
  for j in range(20):
    g = gcd(A[i], B[j])
    A[i], B[j] = A[i] // g, B[j] // g

print(prod(B))