Daily Algorithm - Day 14

Lattice Paths

Starting in the top left corner of a $2 \times 2$ grid, and only being able to move to the right and down, there are exactly $6$ routes to the bottom right corner.
How many such routes are there through a $20 \times 20$ grid?

$20 \times 20$ 격자의 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 가는 길의 개수를 찾는 문제이다.

움직일 수 있는 방향은 오른쪽과 아래 뿐이므로, 모든 경로의 길이는 40이 나올 것이고 오른쪽이 20번, 아래가 20번이 나와야한다. 즉 중복집합 순열이라는 뜻이다.
전체 경우의 수는 $40!$인데 오른쪽이 중복되는 경우가 $20!$, 아래가 중복되는 경우가 $20!$이 있으므로 $\frac{40!}{20!20!}$ 를 계산해주면 된다.

그리고 격자의 수가 바뀔 경우도 대비해보자. $x \times y$ 격자에서 모든 경로의 길이는 $(m+n)$, 오른쪽이 $x$번, 아래가 $y$번 나와야 한다. 즉 길의 갯수는 $\frac{(x+y)!} {x!y!}$ 다.

그렇다면 다음 순서를 통해 코드를 구현해보자.

1. 팩토리얼을 계산해주는 함수를 작성한다.
2. $x \times y$ 격자의 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 가는 길의 개수를 알려주는 함수를 작성한다.

//Python

# 팩토리얼
def factorial (n) :
    factor = 1
    for i in range(1, n+1):
        factor *= i
    return factor

# x*y 격자의 길이 몇개인지 출력
def find_routes (x, y):
    routes = factorial(x+y) / (factorial(x) * factorial(y))
    return int(routes)

print(find_routes(20, 20))

>>> 137846528820

오늘은 여기까지.

-2025.01.04-