파이썬 실전 프로젝트

프로젝트 오일러 18번 문제 - 최대 합 경로찾기

토픽 파이썬 실전 프로젝트 > 파이썬 실전프로젝트

삼각형 모양의 숫자 배열을 따라 내려가면서, 가장 큰 합을 찾는 문제입니다.

경로의 갯수는 2^14 = 16384개 입니다. 일단 그렇게 크지 않을듯 하니, 그냥 경로를 다 찾아보는것도 괜찮은 방법인것 같습니다. 출제자는 그렇게 하지 말고, 좀더 스마트한 방법을 찾아보라고는 하지만, 일단은 그냥 한번 해 보기로 하죠.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

 

 

먼저 데이터 파일을 텍스트파일에서 불러오는 부분입니다. 데이터파일 불러오기 참조

filename = 'q018_data.txt'
with open(filename) as data:
    lines = data.readlines()

for i in lines:
    print(i.rstrip())
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

 

리스트로 저장하기
filename = 'q018_data.txt'
with open(filename) as data:
    lines = data.readlines()
m=len(lines)

numbers=[]
for line in lines:
    print(line.split())
    numbers.append(line.split())
['75']
['95', '64']
['17', '47', '82']
['18', '35', '87', '10']
['20', '04', '82', '47', '65']
['19', '01', '23', '75', '03', '34']
['88', '02', '77', '73', '07', '63', '67']
['99', '65', '04', '28', '06', '16', '70', '92']
['41', '41', '26', '56', '83', '40', '80', '70', '33']
['41', '48', '72', '33', '47', '32', '37', '16', '94', '29']
['53', '71', '44', '65', '25', '43', '91', '52', '97', '51', '14']
['70', '11', '33', '28', '77', '73', '17', '78', '39', '68', '17', '57']
['91', '71', '52', '38', '17', '14', '91', '43', '58', '50', '27', '29', '48']
['63', '66', '04', '68', '89', '53', '67', '30', '73', '16', '69', '87', '40', '31']
['04', '62', '98', '27', '23', '09', '70', '98', '73', '93', '38', '53', '60', '04', '23']

 

함수부분
def findSum(total=0,i=0,j=0):
    total=total+int(numbers[i][j]) # 자기자신의 값 합산
    if i==m-1:                  # 맨 아랫줄(m-1)이면 
        return total            # 합산한 값 리턴 
    else :
        result1 = findSum(total,i+1,j) # 맨아랫줄이 아니면, 아랫줄 호출한후
        result2 = findSum(total,i+1,j+1)
        if result1>result2:            # 리턴된값중 큰것만 다시 리턴.
            return result1
        else:
            return result2

print('final:',findSum())
final: 1074

전체 숫자 트리에서 각 숫자가 하나의 함수라고 한다면, 각 함수는 자신의값을 누적해서 아래의 다른 두 함수로 전달합니다. 그러면 값을 넘겨받은 함수는 자기자신의 값을 더해서 다시 아래로 넘겨주는거죠.

맨 아래에서는 호출할 함수가 더 없으므로, 자기자신의 값을 누적한후 다시 위로 넘겨줍니다. 그러면 리턴받은 함수는 값이 두개가 올라올테니, 크기를 판단해서 큰것만 다시 위로 리턴시킵니다.

그러면 최종 리턴된 값이 가장큰 값이 됩니다.

 

경로찾기

값뿐만 아니라 합산된 숫자들도 알고 싶으면, 매개변수를 하나추가해서 숫자를 문자열로 만들어주면 됩니다.

def findPath(total=0,path='',i=0,j=0): #매개변수 path추default값은 공백('')
    total=total+int(numbers[i][j])
    path=path+','+numbers[i][j]
    if i==m-1:
        return total,path
    else :
        result1 = findPath(total,path,i+1,j)
        result2 = findPath(total,path,i+1,j+1)
        if result1[0]>result2[0]:  #둘이상의 리턴값은 tuple 형.
            return result1
        else:
            return result2

print('final:',findPath())
final: (1074, ',75,64,82,87,82,75,73,28,83,32,91,78,58,73,93')

 

 

 

댓글

댓글 본문