밤에 잠이 안와서 시작한 문제 풀이가 어느덧 3시간이 지났다.
그래서 풀어서 기분은 좋다..^^

문제를 보고 잘못 생각해서 위에서 아래로 큰 수를 찾아가는 거로 계산을 하고 제출을 했는데 오답 표시.

문제를 다시 읽어보니 어떻게 풀어야 할지 조금 막막하다.. 구글신의 도움을 받아 다른 사람이 어떻게 풀었는지를 찾아보았다.

http://www.mathblog.dk/project-euler-18/

위의 링크에 보면 Dynamic Programming 이라는 섹션에 어떤식으로 풀어야 되는지 표시가 되어 있다.

풀이과정

[초기값]

8 5 9 3
2 4 6
7 4
3

[가공값]

1. 8+2 와 5+2 를 비교하여 큰값을 2행 1열(2)위치에 입력
2. 5+4 와 9+4 를 비교하여 큰값을 2행 2열(4)위치에 입력
3. 9+6 과 3+6 을 비교하여 큰값을 2행 3열(6)위치에 입력
4. 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)