정수 삼각형

정수 삼각형
동적계획법(Dynamic Programming) 
3433명 완료

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

코딩테스트 연습 - 정수 삼각형

위에서 부터 아래로 내려오면서 숫자를 더한다. 누적합.
다만 경우의 수가 2개인 경우 max 함수를 사용해 최대값을 선택을 해야 한다. 
최종적으로 마지막 줄에서 최대값을 찾으면 끝.

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

반대로 아래에서 올라오면 더 효율적인 코드가 되는데...

def solution(triangle):
    for y in range(len(triangle) - 2, -1, -1):
        for x in range(len(triangle[y])):
            triangle[y][x] += max(triangle[y + 1][x], triangle[y + 1][x + 1])
    return triangle[0][0]

 

https://comdoc.tistory.com/entry/%EC%A0%95%EC%88%98%EC%82%BC%EA%B0%81%ED%98%95

(파이썬) 정수삼각형 - 동적계획법