밤에 잠이 안와서 시작한 문제 풀이가 어느덧 3시간이 지났다.
그래서 풀어서 기분은 좋다..^^
문제를 보고 잘못 생각해서 위에서 아래로 큰 수를 찾아가는 거로 계산을 하고 제출을 했는데 오답 표시.
문제를 다시 읽어보니 어떻게 풀어야 할지 조금 막막하다.. 구글신의 도움을 받아 다른 사람이 어떻게 풀었는지를 찾아보았다.
http://www.mathblog.dk/project-euler-18/
위의 링크에 보면 Dynamic Programming 이라는 섹션에 어떤식으로 풀어야 되는지 표시가 되어 있다.
풀이과정
[초기값]
8 5 9 3 2 4 6 7 4 3
[가공값]
- 8+2 와 5+2 를 비교하여 큰값을 2행 1열(2)위치에 입력
- 5+4 와 9+4 를 비교하여 큰값을 2행 2열(4)위치에 입력
- 9+6 과 3+6 을 비교하여 큰값을 2행 3열(6)위치에 입력
- 1~3의 스텝을 반복한다.
[소스코드]
import unittest
class TestMaximumPathSumClass(unittest.TestCase):
def testExample(self):
input_str = '''
3
7 4
2 4 6
8 5 9 3'''
value = self.maximum_path_sum(input_str)
self.assertEqual(value, 23)
def testPE67(self):
f = open("/Users/p/Downloads/p067_triangle.txt")
lines = f.readlines()
value = self.maximum_path_sum(''.join(lines))
print(value)
f.close()
def testPE18(self):
input_str = '''
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'''
value = self.maximum_path_sum(input_str)
print("Maximum path sum = ", value)
def maximum_path_sum(self, input_str):
input_str = input_str.strip()
lines = input_str.split('n')
array = []
for line in lines:
if len(line) == 0:
continue
nums_array = line.strip().split(" ")
array.insert(0, nums_array)
for i in range(0, len(array) - 1):
nums_array = array[i]
changed_array = []
for j in range(0, len(nums_array)-1):
v1 = int(array[i][j]) + int(array[i+1][j])
v2 = int(array[i][j+1]) + int(array[i+1][j])
changed_array.append(max(v1, v2))
array[i+1] = changed_array
print(changed_array)
return array[len(array)-1][0]
if __name__ == '__main__':
suite = unittest.TestLoader().loadTestsFromTestCase(TestMaximumPathSumClass)
unittest.TextTestRunner(verbosity=2).run(suite)
Coozplz Blog 