아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).
그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?
def fac(n):
if n == 1:
return 1
return n * fac(n - 1)
for n in range(1, 21):
count = fac(2 * n) / fac(n) / fac(n)
print(f"{n} * {n}격자에서 경로 수: {count}\n")고등학교 확통 단골 문제다. 첫 번째 방법은 모서리마다 숫자를 적고 목적지에 도착할때까지 더해가며 구하는 방법이다. 두 번째 방법은 순열을 이용하는 방법이다. 정직하게 격자 배열을 이동하는 문제이므로 순열을 이용하기로 했다.
위의 2 × 2 격자를 생각해보자.
목적지까지 도착하려면 오른쪽으로 두 번, 아래로 두 번 무조건 이동해야 한다. → →↓↓, →↓→↓,↓→ →↓이런 식으로 이동할 수 있다. →와 ↓을 나열하는 방법을 찾는 것과 같다. 이는 순열로 해결할 수 있다. 모든 가짓수에서 중복되는 경우를 제외하면 된다.
그러니
를 계산하면 된다.
격자를 생각해보면
로 일반화할 수 있다.
팩토리얼은 재귀함수로 구현했다. 출력문장을 반복문 안에 넣었다. 20가지 격자에서 길을 찾는 방법이 모두 출력된다.
C언어에서 위와 같은 방식으로 코드를 짰더니 팩토리얼 값이 너무 커져서 unsigned long long형 표현 범위마저 넘어버렸다. 이런 문제 때문인지 포럼에서는 많은 분들이 길 찾는 첫 번째 방법으로 문제를 해결하셨다. 이차원 배열을 만들어서 1열과 1행에 1을 집어넣고, 다음 행 또는 열에 더한 값을 집어넣고, 마지막 배열요소가 나올떄 까지 쭉 돌리면 답이 나온다. 덧셈이니 값이 팩토리얼만큼 커지진 않고, 속도도 빠르다.