Project Euler. #15. Lattice paths

By | 2013/03/03

Project Euler (http://projecteuler.net/) 문제15

Starting in the top left corner of a 2 * 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 * 20 grid?

2 * 2 격자 사각형에서, 좌측 상단 코너에서 시작하여 오른쪽, 아래 방향으로만 움직일 수 있다. 여기서는 우측 하단 코너까지 가는 경로가 정확하게 6가지가 존재한다.
20 * 20 격자 사각형에서는 얼마나 많은 경로가 존재하는가?

projecteuler15

처음에 이 문제를 보고 약간 당황했다. 이런 문제는 도대체 어떤 식으로 프로그래밍을 이용하여 풀수가 있는가...

일단 오른쪽 방향의 이동을 1, 아래 방향의 이동을 0 이라고 놓고, 20 * 20 = 40 개의 칸을 움직이는 모든 경우의 수를 리스트로 만들어서 저장하고, 그 모든 경우의 수가 몇 개인지를 세어보기로 했다.


ways = []
way = []
def findAWay(way):
    if way.count(0)==20:
        for i in range(0, 40-len(way)):
            way.append(1)
        ways.append(way[:])
        return None
    elif way.count(1)==20:
        for i in range(0, 40-len(way)):
            way.append(0)
        ways.append(way[:])
        return None
    else:
        findAWay(way+[0])
        findAWay(way+[1])

findAWay(way)
print len(ways)

재귀를 이용하여 빈 리스트에 0이나 1을 하나씩 계속해서 넣되, 오른쪽으로는 20여칸이 최대, 아래쪽으로도 20여칸이 최대이므로, 0 또는 1의 개수가 20이 되면 나머지는 각각 1 또는 0 으로 채워넣어서 해당 리스트의 요소를 40개로 채운 뒤 하나의 경우의 수로 취급하기로 했다. 이런 방식은 격자사각형의 크기가 10 * 10 만 넘어가도 엄청난 계산 양으로 인해 모든 경우의 수를 다 구할 때 까지 기다릴 수가 없다. 식당에 가서 밥을 먹고 갔다오니 답이 나와있기는 커녕 IDLE이 다운되기 일보 직전의 상태에 있었다. 이렇게 해서는 답을 구한다고 해도 의미가 없다. 분명히 뭔가 더 효율적인 방법이 존재할텐데...

위의 코드에 print 를 삽입하고 실행해보니 무수히 많은 경우의 수들이 계속해서 출력되고 있었다.

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1]
...
...
...

이 패턴을 보다보니 뭔가 떠오르는 것이 조합. 총 40여개의 공에서 20개의 공을 고르는 경우의 수를 구하는 것과 동일하다는 생각이 들었다. 지금 이 문제는 총 40개의 빈칸을 20개의 0(아래쪽)과 1(오른쪽)로 채우는 경우의 수를 구하여야 한다. 어짜피 0들끼리의, 또는 1들끼리의 순서는 상관이 없다. 그렇다면 바로 '조합'을 계산하여야 한다! 어떻게 구하지?

학창시절 내 수학의 정석은 집합 부분만 손때가 더럽게 묻어있었다. 확률과 통계는 제일 뒷쪽의 챕터였기 때문에 나의 고등학교 졸업식까지도 깨끗한 상태로 보존되어 있었던 것 같다. 아, 중3 때도 확률과 통계를 배웠던가? 내 인생에서 수학의 전성기는 중2때 절정에 달했고, 중3때는 땅을 기었기에 배웠던 것 같으면서도 기억이 나질 않는다. 하지만 상관없다. 검색을 하면 되니까.

combination


def fact(n):
    if n==1:
        return 1
    return n*fact(n-1)

print fact(40)/(fact(20)*fact(20))

자 이렇게 간단하게 정답을 계산해 낼 수 있었다.

이번 문제는 프로그래밍하고 관련이 있다기보다는 수학적 사고력을 요하는 문제였다. 어떻게 이 문제를 풀 것인가? 처음에 모든 경우의 수를 리스트에 저장해보려다가 좌절하고 나서 며칠 쉬었었는데, 조용한 새벽, 이 문제를 풀며 아침을 맞이할 각오를 했더니 금방 전구가 반짝이며 이 문제를 해결해냈다. 덕분에 작년에 시간이 나면 풀어봐야지 싶어서 새로 구입해놓고 단 한번도 펼쳐보지 않은 수학의 정석 책을 꺼내들어 틈틈이 공부해야할 필요성을 절실히 느끼게 된다.