[프로그래머스] 정수 삼각형 파이썬 풀이

정수삼각형

풀이

문제의 규칙을 하나하나 따져봤을 때, 다음의 규칙을 알 수 있다.

i	횟수	예시
1	1	7
2	2	(7+3), (7+8)
3	4	(7+3+1), (7+8+1), (7+8+0)

• i 가 증가함에 따라 2^(n-1)번의 횟수가 적용된다는 것을 알 수 있다.
  • 문제에서 주어진 입력의 크기가 1 <= N <= 500 이기 때문에 DFS 혹은 BFS를 사용하면 2^499번의 연산을 수행해야하기 때문에 이 방법으로는 풀 수 없다.
• 이전의 연산에서 사용된 값을 다음의 연산에서 사용한다.

그렇기 때문에 이 문제에서는 DP를 사용하여 풀어야 한다.

• 이제 문제에서 규칙을 찾아보자
  • [i][j]의 연산 결과를 얻기 위해서는 [i-1][j], [i-1][j+1] 까지의 값에서 현재 [i][j]값까지 더한 값 중 더 큰 값을 저장해주면 된다.
  • 이를 유의해서 코드를 작성하면 다음과 같이 작성할 수 있다.

코드

def solution(triangle):
    length = len(triangle)
    dp = [[0] * length for _ in range(length)]
    dp[0][0] = triangle[0][0]

    for i in range(length - 1):
        for j in range(len(triangle[i])):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + triangle[i + 1][j + 1])

    return max(dp[-1])