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)
[출처 - projecteuler.net/]
이번 문제는 꼭대기에서 아래로 길을따라 내려오면서, 지나온 위치의 값들을 더해갈텐데... 가장 아래에 도착했을때 그 값이 가장큰 아이의 결과를 구하는 문제입니다. 여러가지 방법이 있겠지만... 나중에 67번 문제에서는 더 어렵다고 하니... 100개의 줄이 들어온다고 하는데, 그럼 경우의 수도 엄청나게 많을 것 입니다.
하지만 일단 이번 문제를 풀어보는데만 집중해 보겠습니다.
1. Basic
꼭대기부터 내려올때의 이런저런 가지치기의 조건을 확인해 보겠습니다.
마치 꼭대기부터 물을 가득채워서 아래로 흘러 내려서 맨 아래까지 꽉채우는 그런 모습을 볼 수 있습니다. 결국 제일 위의 값은 아래의 모든 위치에 영향을 미치고... 부분적으로 떼어낼경우, 그 부분의 가장 위의 값은 그에 속한 아래까지 영향을 미치게 됩니다.
그럼 2가지를 고려해서 계산하면 되겠습니다.
- 어느 한 지점의 값은, 자기에게 영향을 주는 바로 위의 계산결과 값과 자신의 합이 그 지점의 값이고,
- 어느 한 지점의 값의 최대값을 고려하기 위해서는, 자신에게 영향을 주는 최대 2가지 경우에 대해서 최대값을 구해야 함
해당 2가지를 그림으로 표현하면, 위와 같습니다. 그렇다면 이제 이것을 어떻게 코드로 구현해야 할까요??
첫번째 줄은 그냥 기준이 될 것이고...
두번째 줄은 첫번째 줄의 값과 영향있는 두번째 줄의 값과 합으로 그 결과가 주어질 것입니다.
세번째 줄은 이제 (5)의 경우와 같이 양쪽에서 영향을 받는 수가 있기 때문에 최대값을 그 결과로 정해야 합니다.
[소스 코드]
import time
if __name__ == '__main__':
tc = int(input())
start = time.time()
for t in range(tc):
line = int(input())
res = []
for l in range(line):
inp = [int(a) for a in (input().strip().split(' '))]
if len(res) == 0:
res = inp
else:
temp = [0] * (l+1)
for i in range(len(res)):
temp[i] = max(temp[i], res[i]+inp[i])
temp[i+1] = max(temp[i+1], res[i]+inp[i+1])
res = temp
print(res)
print("결과 : ", max(res))
end = time.time()
print("소요시간 : ", end - start)우선 해당 입력이 여러개의 숫자로 들어오기 때문에, python을 통한 input에서는 string으로 받을 것 입니다. 따라서, 양쪽 공백을 제거하고... ' ' 공백을 기준으로 split을 수행하여 list의 숫자형대로 변환하여 저장을 해 줍니다.
inp = [int(a) for a in (input().strip().split(' '))]
print(inp)
====================================================
[12, 13, 14, 15]그럼 이제는 실제로직을 구현하겠습니다. 매번 현재 입력이 되는 행의 위치만큼 결과를 저장하는 list를 생성하고... 이전 결과를 기준으로 그 결과가 이번 입력된 행에 영향을 미치는 양쪽에 대해서 값을 구하고, 그 최대값을 신규 결과 list에 저장하는 방식을 사용합니다.
그렇게 되면... 각 라인이 진행될때 마다의 최대값 현황 및 결과는 아래와 같습니다.
[입력]
3
7 4
2 4 6
8 5 9 3
===============================
[3]
[10, 7]
[12, 14, 13]
[20, 19, 23, 16]
결과 : 23
소요시간 : 0.07200002670288086자 그렇다면... 실제 문제의 입력을 넣어보겠습니다.
[결과]
[75]
[170, 139]
[187, 217, 221]
[205, 252, 308, 231]
[225, 256, 390, 355, 296]
[244, 257, 413, 465, 358, 330]
[332, 259, 490, 538, 472, 421, 397]
[431, 397, 494, 566, 544, 488, 491, 489]
[472, 472, 520, 622, 649, 584, 571, 561, 522]
[513, 520, 592, 655, 696, 681, 621, 587, 655, 551]
[566, 591, 636, 720, 721, 739, 772, 673, 752, 706, 565]
[636, 602, 669, 748, 798, 812, 789, 850, 791, 820, 723, 622]
[727, 707, 721, 786, 815, 826, 903, 893, 908, 870, 847, 752, 670]
[790, 793, 725, 854, 904, 879, 970, 933, 981, 924, 939, 934, 792, 701]
[794, 855, 891, 881, 927, 913, 1040, 1068, 1054, 1074, 977, 992, 994, 796, 724]
결과 : 1074
소요시간 : 0.07299995422363281소요시간이 0.07초를 기록하였습니다. 실제로 67번 문제에서 적용을 해봐야 알겠지만... 왠지 통과 되지 않을까 싶습니다.
- Ayotera Lab -
댓글