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

😎코딩테스트 연습>동적계획법(Dynamic Programming)>정수 삼각형

---

📘 문제풀이1

아래에서 위로 더해 max값을 찾는 방법

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

📘 문제풀이2

위에서 아래로 더해 max값을 찾는 방법

def solution(triangle):    
    tri = [[0]*i for i in range(1, len(triangle[-1])+1)]
    tri[0][0] = triangle[0][0]
    
    for i in range(len(triangle)-1):
        for j in range(len(triangle[i])):
            tri[i+1][j] = max(tri[i+1][j], tri[i][j] + triangle[i+1][j])
            tri[i+1][j+1] = max(tri[i+1][j+1], tri[i][j] + triangle[i+1][j+1])
    
    return  max(tri[-1])