프로젝트 오일러 015

문제

15번 문제

20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

사이냅소프트

문제에서 예로 든 2x2 격자에서 그림으로 표현하지 않고 오른쪽으로 진행하는 것을 a, 아래로 진행하는 것을 b라고 하면 6개의 경로는 다음과 같이 표현할 수 있습니다.

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

이는 ['a', 'a', 'b', 'b']에서 같은 것끼리의 순서를 무시하고 순열을 만드는, 즉 중복된 것을 포함하는 순열의 문제와 동일합니다. 경로의 개수만 계산하면 되기 때문에, 남은 부분은 간단합니다. 공식은 40! ÷ 20! ÷ 20! 입니다.

팩토리얼은 1부터 n까지의 곱이기 때문에 아래와 같이 간단히 계산하면 됩니다.

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 × ∙∙∙ × 22 × 20) ÷ (20 × 19 × ∙∙∙ × 1) 이니까, 분모, 분자에 각각 20개의 정수가 있고 모든 분모의 인수를 약분하는 것이죠.

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))