파이썬_실전 프로젝트

프로젝트 오일러 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(40C20) 공식한줄이면 끝납니다.

또는  nCr 계산을 공식이 아니라, nC0=1, nC1=n 이라는 특성을 이용해서, 함수의 재귀호출을 이용해서 계산할수도 있습니다.

 

방법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)

 

댓글

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