[프로그래머스] 동적계획법 2. 정수 삼각형

문제

---

풀이

1. 각 노드까지의 최댓값을 저장

2. 맨 아래 줄까지 반복

3. 맨 아래 줄 중 가장 큰 값 반환

def solution(triangle):
    for i in range(len(triangle) - 1):
        for j in range(len(triangle[i+1])):
            if j == 0: # 각 줄의 첫 번째 노드인 경우 오른쪽 부모의 값만 더함
                triangle[i+1][j] = triangle[i][j] + triangle[i+1][j]
                continue;
            if j == len(triangle[i+1]) - 1: # 각 줄의 마지막 노드인 경우 왼쪽 부모의 값만 더함
                triangle[i+1][j] = triangle[i][j-1] + triangle[i+1][j]
                continue;
            #중간 노드인 경우 왼쪽 부모와 오른쪽 부모의 값 중 큰 값과 자기 자신을 더한 값을 저장
            triangle[i+1][j] = max(triangle[i][j-1], triangle[i][j]) + triangle[i+1][j]

	#마지막 줄에서 가장 큰 값을 반환
    return max(triangle[len(triangle)-1])

 

간만에 검색 없이 풀었다. 뿌듯ㅎ

---

다른 사람의 풀이

solution = lambda t, l = []: max(l) if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])

???!?

해석불가

그렇다고 한다....