파이썬_실전 프로젝트

프로젝트 오일러 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?

 

 

조합(combination)을 알고계신분은, 코딩도 필요없이, nCr(예제는 4C2, 문제는 40C20) 공식한줄이면 끝납니다. 예제에서 가로방향 화살표, 세로방향 화살표가 2개씩 총 4개가 있다고 가정할때, 4개 화살표의 자리를 배치하는 경우의 수와 같습니다. 4개중에 2개의 자리를 정하는 문제이므로, 4C2 가 됩니다.

문제도 마찬가지로, 20x20 의 격자는, 세로이동 20번, 가로이동 20번이므로, 총 40개의 이동단위를 자리배치하는 경우의 수와 같으므로 40C20 이 됩니다.

 

조합을 사용하지 않더라도 사각형을 작은 사각형으로 계속 분해해 가는식으로 계산을 해서, 함수의 재귀호출을 이용할수도 있습니다. 2x2 사각형은 2x1사각형 두개의 경우의 수의 합과 같고, 2x1 사각형은 경우의 수가 3입니다.(nx1 사각형 = n+1 의 경우의 수). 그러므로 두배를 하면 6이 됩니다. 

같은 방법으로 문제에 적용하면 20x20 사각형은 20x19 사각형 두개의 경우의 수의 합과 같고, 20x19 는 다시 19x19와 20x18로 분해가 됩니다. 분해를 계속 해가다 보면, 결국은 모두 가장자리에 닿게 되므로, 20x1,19x1,18x1,,, 가장자리 사각형에 도달하게 되고, 각 가장자리 사각형의 경우의 수는 20x1은 21, 19x1은 20 으로 nx1 사각형은 n+1로 정해져 있습니다. 이것을 코드로 표현하면 아래와 같습니다.(결국 combination의 성질과 같기때문에 combiantion으로 표현해도 무방합니다.)

 

방법1
def combination(n1,n2):
    if n2==0:
        return 1
    elif n2==1:
        return n1
    elif n1==n2*2:
        return combination(n1-1,n2-1)*2
    else:
        return combination(n1-1,n2)+combination(n1-1,n2-1)

print(combination(40,20))

한가지 문제점은, 위와 같이 만들면, 격자 전체를 다 계산하게 되는데, 재귀호출이 늘어날수록, 계산량이 기하급수적으로 많아지고 시간이 오래 걸립니다.

 

방법2

좀더 빠르게 계산하는 방법은, 정방형이기때문에, 대각선(/)상의 점들을 통과하는 경로의 수는 양쪽이 동일하고, 제곱을 해주면 해당점을 통과하는 경로의 수가 됩니다. 그리고 대각선상의 점들을 합산하면 됩니다.

def grid(r,c):
    if c==0 or r==0:
        return 1
    elif r==1:
        return c+1
    elif c==1:
        return r+1
    else:
        return grid(r,c-1)+grid(r-1,c)

i=0;dim=20;total=0  #20x20 이라는 의미로, dim값 20으로 설정.
while i<=dim:
    grid_sum=0
    print('grid:',i,dim-i)  
    grid_sum=grid(i,dim-i)**2  #함수리턴값을 제곱해서 합산.
    print(grid_sum)
    total = total + grid_sum
    i+=1

print(total)

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
code builder
현재 버전
선택 버전
graphittie 자세히 보기