[Backjoon] 정수 삼각형

1932번 문제인 정수 삼각형은 동적 계획법으로 풀 수 있는 문제이다. 맨 처음 접근할 때 상향식 동적 계획법으로 풀이하려고 했으나, 그리디 방식으로 설계를 해버려서 시간을 낭비했다. 아에 하향식으로 접근해서 재귀적으로 풀이해 문제를 맞출 수 있었다. 그러나 상향식으로 풀이하면 실행속도를 아주 빠르게 가져갈 수 있으니, 계속 상향식으로 접근하는 연습을 해야겠다. 아래의 코드는 하향식 접근법이다.

 

import sys
sys.setrecursionlimit(10**6)

def find_sum(idx_row, idx_selected, triangle, cache):
    if idx_row == len(triangle):
        return 0

    if cache[idx_row][idx_selected] != 0:
        return cache[idx_row][idx_selected]
    else:
        result = 0
        for idx in range(len(triangle[idx_row])):
            if idx_selected <= idx <= idx_selected + 1:
                result = max(result, find_sum(idx_row + 1, idx, triangle, cache) + triangle[idx_row][idx])
        cache[idx_row][idx_selected] = result
        return result

if __name__ == "__main__":
    size = int(sys.stdin.readline())

    triangle = []
    for _ in range(size):
        temp = list(map(int, sys.stdin.readline().split(" ")))
        triangle.append(temp)

    cache = [[0 for _ in range(len(triangle))] for _ in range(len(triangle))]

    print(find_sum(0, 0, triangle, cache))