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

문제

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3

풀이

대게 이런 삼각형 문제들은 행 단위로 구분시켰을 때
위 아래 행 간의 구성에 대해 이해하면 풀이가 시작되는 것 같다.

    [7] ---------- 0
   [3, 8] -------- 1
  [8, 1, 0] ------ 2
 [2, 7, 4, 4] ---- 3
[4, 5, 2, 6, 5] -- 4

문제 예시를 기준으로 생각해봤을 때,
2행의 3, 8은 선택권 없이 7과 더해진다.
3행의 8, 0은 선택권 없이 3, 8과 더해지지만,
3행의 1에게는 선택권이 생긴다.

즉, 양끝의 값들은 무조건 더하면 되고,
중간 값들은 양측 중에 더 큰 값과 더하면 해결이 된다!

def solution(triangle):
    for row in range(1, len(triangle)):
        for col in range(row+1):
            if col == 0:
                triangle[row][col] += triangle[row-1][0]
            elif col == row:
                triangle[row][col] += triangle[row-1][col-1]
            else :
                triangle[row][col] += max(triangle[row-1][col-1],triangle[row-1][col])
    
    return max(triangle[col])

더 나은 풀이

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])])

더 나은진 솔직히 모르겠고, 신기했던 코드.
한 층씩 제거하면서 지나가는 것 같은데, 자세한 동작 방식은 직접 돌려보지 않으면 이해하기 어려운 것 같다.