[프로그래머스] 정수 삼각형 - python (레벨 3)

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

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

풀이

문제를 보았을때 알수있는 힌트

bfs나 dfs를 통해 백트래킹해서 문제를 푼다면 시간 초과가 날수 있는 문제이다.

triangle 과 같은 리스트의  dp를 만들고 이전의 값의 더하면서 최대값이 되는 값을 유지하며 진행하면 쉽게 풀리는 문제이다.

예를 들어 1행의 7을 2행의 3과 8에 넣어 2행 dp에 [10,15]를 가지게 한다.

다음으로 2행의에서 3행으로 갈수있는 방법으로 2행의 1번째는 3행의 1,2번째를 갈수있고[18,11] 2행의 2번째는 3행의 2,3번[16,15]을 갈수있다. 이때 2번째가 겹치는데 11,16중에 큰값인 16을 선택하게 한다. 총 3행의 dp는 [18,16,15]가 된다.

이렇게 마지막까지 반복하는 코드를 작성하고 마지막 행의 최대값을 result에 나오게 하면 끝이난다.

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

    return max(dp[-1])

https://github.com/dydwkd486/coding_test/blob/main/programmers/정수%20삼각형.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리