원문:
Problem 15
Starting in the top left corner of a 2
2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20
20 grid?
2
2 격자의 왼쪽 위의 모서리에서 시작하면, 오른쪽 아래의 모서리까지 (뒤로 돌아가는 것 없이) 6가지 길이 있다.
...
20
20 격자에는 얼마나 많은 길이 있는가?
수학적으로는 매우 간단한 문제이다. 오른쪽으로 가는 것을 1, 아래로 가는 것을 0이라고 했을 때 각각 20개의 1과 0을 중복되지 않게 배치했을 때의 총 개수를 묻는 문제와 같다.
즉, 오른쪽으로 쭉 간 후 아래로 쭉 내려가는 경우는 1111111111111111111100000000000000000000과 같이 표현할 수 있다.
위의 개수를 세는 방법은 40!/(20! * 20!) 이다. 이것을 계산해주면 된다.
접기
수학을 사용하지 않고 직접 코딩을 해보았다.
Python>>> def search(x, y) :
if x < 10 :
search(x+1, y)
if y < 10 :
search(x, y+1)
if x==10 and y==10 :
global count
count += 1
>>> exec('''s = time.time()
count = 0
search(0,0)
print(count)
print(time.time() - s)''')
184756
0.307009935379
>>> def search(x, y) :
if x < 13 :
search(x+1, y)
if y < 13 :
search(x, y+1)
if x==13 and y==13 :
global count
count += 1
>>> exec('''s = time.time()
count = 0
search(0,0)
print(count)
print(time.time() - s)''')
10400600
16.9886009693
함수 구현은 재귀로 해서 오른쪽 위에서 왼쪽 아래로 검색하도록 했다. 그런데 예상 했던 만큼 시간이 엄청 오래 걸린다. 13X13만 계산해도 17초인데, 20X20은 엄청 걸릴 것이다.(급수적으로만 따져도 개수가 1000배이므로 시간이 1000배 증가하면 17000초가 걸린다.)
접기
다른 방법을 사용하면 아래와 같게 된다.
Python 2>>> def search(i, j) :
count = 0
def f(x, y, i, j) :
if x < i :
f(x+1, y, i, j)
if y < j :
f(x, y+1, i, j)
if x==i and y==j :
nonlocal count
count += 1
f(0, 0, i, j)
return count
>>> sum(search(20-x, x)**2 for x in range(21))
오른쪽 위에서 왼쪽 아래로 대각선을 그어서 반으로 나누면 대칭이 된다. 따라서 그 대각선에 위치한 점들까지 갈 수 있는 경우의 수를 계산하고 대칭이므로 끝까지 가는데 각각마다 제곱의 개수만큼 길이 존재한다. 이것을 다 합하면 되는데, 위를 실행하는 시간은 1초가 안 걸렸다.
접기
How many routes are there through a 20
댓글 없음:
댓글 쓰기