파이썬_실전 프로젝트

프로젝트 오일러 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 biggest_sum(i=0,j=0):
    if i==m-1:
        return numbers[i][j]
    else :
        num1=biggest_sum(i+1,j)
        num2=biggest_sum(i+1,j+1)
        if num1>num2:
            return int(numbers[i][j])+int(num1)
        else :
            return int(numbers[i][j])+int(num2)

i,j 는 앞서 만든 2차원 리스트의 행과 열이고, 함수는 삼각형의 꼭지점에서부터 아래로 하나씩 내려가면서, 각각 아래방향으로 i,j 를 인자로 넘겨주며 두개의 "자기자신" 다시 호출하고, 호출된 함수 역시 같은 작업을 하고, 이런식으로 끝까지 내려갑니다. 각 함수의 리턴값은 아래 두개의 리턴값중 큰것과 자기자신의 합입니다.

그리고 맨 아래줄  i==m-1 에서는 재귀호출을 하지 않고, 자기자신의 값만 리턴해줍니다.

 

전체코드
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())
        
def biggest_sum(i=0,j=0):
    if i==m-1:
        return numbers[i][j]
    else :
        num1=biggest_sum(i+1,j)
        num2=biggest_sum(i+1,j+1)
        if num1>num2:
            return int(numbers[i][j])+int(num1)
        else :
            return int(numbers[i][j])+int(num2)

print(biggest_sum())
['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']
1074

 

댓글

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