프로그래머스 DP_정수 삼각형

프로그래머스 DP(다이나믹 프로그래밍) 정수 삼각형 문제 풀이입니다.

 

 

문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

---

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

입출력 예

 

triangle : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

result : 30

---

풀이법

 

왼쪽 또는 오른쪽으로 이동 하면서 합해주면 되는 문제이다.

 

첫번째 행은 7

두번쨰 행은 10, 15

세번째 행은 18, max(11, 16), 15 

...

 

 

이런식으로 새로운 배열을 만들어 주도록 하자.

 

즉, 좌 우측 끝값 연산은 따로해주고 중간에 끼인 연산들은 합의 최대값만 선택하면 된다

 

ex) 7 - 3 - 1, 7 - 8 - 1 순서로 노드를 타고내려오면, 7-3-1은 버려도된다.

 

---

코드 

def solution(triangle):
    dp = [triangle[0]]

    for i, row in enumerate(triangle):
        if i == 0:  # i == 0일때는 반복문 실행하지 않고 넘김
            continue
        lst = []  # dp 리스트에 append 해 줄 배열
        rowlength = len(row) - 1  # 끝 노드임을 지정해주기 위함

        for k, value in enumerate(row):
            if k == 0:  # 제일 왼쪽 노드 처리를 위함
                lst.append(dp[i-1][0] + value)
            elif k == rowlength:  # 제일 오른쪽 노드 처리를 위함
                lst.append(dp[i-1][rowlength - 1] + value)
            else: #제일 좌측, 우측 노드가 아니라면 k-1, k 번째 노드를 비교해서 큰값을 더해줌
                lst.append(max(dp[i - 1][k - 1], dp[i - 1][k]) + value)

        dp.append(lst)

    return max(dp[-1])