[프로그래머스] 정수삼각형

문제 이해하기

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 하시오.

 

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

문제 해결 방법 설명하기

1. 최대값을 찾는 방법

최대값이 되는 경로를 찾기 위해서는 모든 가능한 경로를 탐색해야 합니다. 그러나 모든 경로를 매번 계산하려고 하면 제한된 시간 내에 문제를 해결할 수 없습니다. 따라서 이전에 저장한 정보를 활용하는 방법이 필요합니다.

 

제가 선택한 방법은 트리의 각 노드에 대해 해당 노드가 속한 경로의 최대값을 저장하는 것입니다. 이를 위해 트리의 높이와 각 높이에서 선택한 위치를 저장하여 중복 계산을 방지합니다. 이렇게 하면 500 * 500의 연산으로도 문제를 해결할 수 있습니다.

코드

def search(triangle, idx, pos, cache):
    if idx == len(triangle):
        return 0
    
    if cache[idx][pos] != -1:
        return cache[idx][pos]
    
    left = pos
    right = pos + 1
    
    cache[idx][pos] = triangle[idx][pos] + max(search(triangle, idx+1, left, cache), search(triangle, idx+1, right, cache))
    return cache[idx][pos]
    

def solution(triangle):
    answer = 0
    cache = [[-1 for _ in range(501)] for _ in range(501)]
    answer = search(triangle, 0, 0, cache)
    return answer


if __name__ == "__main__":
    triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
    print(solution(triangle))  # 30

코드 리뷰

트리의 하단에서 부터 상단으로 전파하는 모습이다.

def solution(triangle):

    height = len(triangle)

    while height > 1:
        for i in range(height - 1):
            triangle[height-2][i] += max([triangle[height-1][i], triangle[height-1][i+1]])
        height -= 1

    answer = triangle[0][0]
    return answer

 

 

배운점 정리하기

거꾸로 전파시켜서 기존에 배열에 값을 더해주는 방식이 대단한 것 같다.생각해보면 값이 최대가 될려면 위에서 부터 계산하더라도 최대의 값만 더해주면 최대값이 된다. 따라서 추가적인 배열은 필요없게 된다.