[Python] [Programmers] 정수 삼각형(43105)

💡 문제 해결

1. 삼각형의 크기와 같은 dp리스트 생성
2. 가장 꼭대기 값을 미리 설정
3. 열과 행을 반복문을 통해 탐색하며 이동 경로로 가능한 장소의 최대값을 현재 위치값과 합친 결과를 저장
4. 마지막 열의 최대값을 반환

📌 dp문제의 개념을 아는데 가장 기본이라고 생각

🧾 문제 설명

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 
아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 
예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 
거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

문제보기

🖨 입출력

📝 풀이

def solution(triangle):
    answer = 0

    N = len(triangle)
    dp = [[0] * n for n in range(1, N + 1)]
    dp[0][0] = triangle[0][0]

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

    answer = max(dp[-1])

    return answer

• 출처: Programmers
• 링크: https://programmers.co.kr/learn/courses/30/lessons/43105