문제
프로그래머스 level 3 정수 삼각형 문제를 풀었습니다.
스킬 체크에서 만난 문제입니다. 알고리즘을 어떤 것으로 적용해야할지 갈팡질팡하다가, DFS로 생각하고 구현했더니 시간초과를 받았습니다. 스킬체크가 끝나고 해당 문제를 찾아보니 DP로 분류되어있었습니다. 아.. 생각해보면 직전의 결과값이 바로 다음의 결과값에 영향을 미치고, 모든 노드를 탐색하기에는 중복되는 루트가 굉장히 많아서 당연한 것이었는데, DP를 떠올리질 못했습니다…
왜 그랬을까… 곰곰히 생각을 해보면 경험치 부족인 것 같습니다. 문제에서 주어지는 자료구조가 이런 형태 + 여러 루트를 타고 갔을 때의 최대값을 구하는거면 늘 DFS나 BFS를 했었으니까요. 제대로 알지 못하기 때문에, 아는 선에서만 얕게 알고리즘을 골라서 이런 일이 벌어지는 듯 합니다.
오늘도 화이팅! 새로운 문제를 접하고 시야를 넓혔으니 만족합니다 👍
풀이
def solution(triangle):
DP = [[0]*len(triangle[-1]) for _ in range(len(triangle))]
DP[0][0] = triangle[0][0]
for y, nodes in enumerate(triangle) :
if y == 0 : continue
L = len(nodes)-1
for x, node in enumerate(nodes) :
if x == 0 :
DP[y][x] = DP[y-1][x]
elif x == L :
DP[y][x] = DP[y-1][x-1]
else :
DP[y][x] = max(DP[y-1][x-1], DP[y-1][x])
DP[y][x] += triangle[y][x]
return max(DP[-1])