구연지

def calculate_max_value(row, col, triangle): if row == len(triangle)-1: # depth가 1이라는 것은 가장 마지막 숫자들을 본다는 것 return triangle[row][col] else: num1 = calculate_max_value(row+1, col, triangle) + triangle[row][col] num2 = calculate_max_value(row+1, col+1, triangle) + triangle[row][col] # print(num1) # print(num2) # # print(max(num1, num2)) return max(num1, num2) # depth가 2 이상이면 col이 자기랑 같거나 자기보다 1 큰 경우 중에서 최댓값 def solution(triangle): answer = calculate_max_value(0, 0, triangle) return answer print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

import copy def solution(triangle): # 층의 개수 = 숫자 개수 max_nums = [0]*len(triangle) print(max_nums) max_nums[0] = triangle[0][0] print(max_nums) for i in range(1,len(triangle)): # 값을 업데이트하면서 N-1번째의 값이 소실될 수 있으므로 복사해둔다. max_nums1 = copy.copy(max_nums) # 삼각형의 왼쪽 변과 오른쪽 변 max_nums[0] = max_nums1[0] + triangle[i][0] max_nums[i] = max_nums1[i-1] + triangle[i][i] # 나머지 for j in range(1, i): max_nums[j] = triangle[i][j] + max(max_nums1[j-1], max_nums1[j]) print(max_nums) return max(max_nums) print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))