[프로그래머스]level3-정수 삼각형-Python[파이썬]

문제링크

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

문제설명

알고리즘

접근1. 다익스트라
각 삼각형의 위치를 노드로 하여 합이 최대가 되도록 모든 노드를 탐색하는 방법을 써봤다.
정확성 테스트는 모두 통과했으나.. 역시나 효율성 테스트는 한개도 통과 못했다..

• 이때 주의할 점 : 값이 큰 것을 가장 먼저 뽑아야 하므로 최대힙으로 구현해야한다.

import heapq
# 남, 동남      
di_lst = [1, 1]
dj_lst = [0, 1]
def dijkstra(start, triangle, distance):
    n = len(triangle) # 5
    m = len(triangle[-1]) # 5
    hq = []
    distance[0][0] = triangle[0][0]
    heapq.heappush(hq, (-triangle[0][0], 0, 0))
    while hq:
        dist, i, j = heapq.heappop(hq)
        dist = dist * (-1)
        if distance[i][j] > dist:
            continue
        for di, dj in zip(di_lst, dj_lst):
            ni = i + di
            nj = j + dj
            if ni >= 0 and nj >= 0 and ni < n and nj < m:
                cost = dist + triangle[ni][nj]
                if cost > distance[ni][nj]:
                    distance[ni][nj] = cost
                    heapq.heappush(hq, (-1 * cost, ni, nj))
                

def solution(triangle):
    n = len(triangle) # 5
    m = len(triangle[-1]) # 5
    distance = [[0] * m for i in range(n)]
    start = (0, 0)
    dijkstra(start, triangle, distance)    
    return max(distance[-1])

접근2. DP (동적계획법)
역시나 이 문제는 DP로만 풀어야 하나보다..
상향식(bottom-up) 방법으로 풂. 생각보다 쉬웠다.
앞으로 DP를 너무 겁먹어 하지 말자..!

def solution(triangle):
    d = [[0] * len(triangle)for i in range(len(triangle))]
    d[0][0] = triangle[0][0]
    for i in range(1, len(triangle)): # i번째 줄
        for j in range(0, i+1): # i=1 -> j=0, 1 // i=2 -> j=0,1, 2
            if j-1 < 0:
                d[i][j] = d[i-1][j] + triangle[i][j]
            else:
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j]
    return max(d[-1])