[프로그래머스/파이썬] 동적계획법 정수 삼각형

bye9·2021년 2월 15일
0

알고리즘(코테)

목록 보기
66/130

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


알고리즘 분류

  • 다이나믹프로그래밍

문제풀이

백준 1932 정수 삼각형과 동일한 문제이다.

규칙을 찾으면 쉽게 접근이 가능하다.

소스코드

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]
            elif j==len(triangle[i])-1:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                triangle[i][j]=max(triangle[i-1][j-1], triangle[i-1][j])+triangle[i][j]

    return (max(triangle[len(triangle)-1]))

0개의 댓글