정수 삼각형

• 2차원 DP 처음 배울때 접하는 대표적인 연습문제로 알고 있었는데 1994년 IOI 문제였다. BOJ의 정수 삼각형도 동일한 문제.
• 각 줄을 좌측정렬시켜서 직각삼각형 모양으로 만들어서 각 수를 좌표에 매칭시키자. 이제 dp[r][c]를 꼭지점에서 (r,c) 까지 이어지는 경로의 최대 합이라고 하면, 점화식은 dp[r][c] = num[r][c] + max(dp[r-1][c-1], dp[r-1][c]) 과 같은 형태가 된다. O(n^2)에 테이블을 모두 채울수 있다. 또한 현재 열에 대해서 값을 구하는 것이, 이전 열에 대한 값만으로 계산 가능하므로 슬라이딩 윈도우 방식으로 메모리를 줄일 수 있다. 테이블을 모두 채운 다음에는 max(dp[N][0], …, dp[N][N])을 리턴하면 된다.
• 위 방법도 충분히 간단하지만, c가 0일때, c가 r-1 일때 등에 대해서 추가 처리가 필요하다. 식을 살짝 바꿔서, 바닥에서 출발해서 (r,c)까지 가는 경로를 찾는 식으로 계산하면 좀 더 코드가 깔끔해진다. 두가지 코드를 다 첨부했다

"""Solution code for "Programmers 43105. 정수 삼각형".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43105
- Solution link: http://www.teferi.net/ps/problems/programmers/43105
"""


def solution(triangle):
    dp_cur = []
    for i, triangle_row in enumerate(triangle):
        dp_cur, dp_prev = [], dp_cur
        for j, num in enumerate(triangle_row):
            if j == 0:
                dp_cur.append(dp_prev[j] + num)
            elif j < i - 1:
                dp_cur.append(max(dp_prev[j - 1], dp_prev[j]) + num)
            else:
                dp_cur.append(dp_prev[j - 1] + num)
    return max(dp_cur)

"""Solution code for "Programmers 43105. 정수 삼각형".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43105
- Solution link: http://www.teferi.net/ps/problems/programmers/43105
"""


def solution(triangle):
    dp_cur = [0] * (len(triangle) + 1)
    for triangle_row in reversed(triangle):
        dp_prev = dp_cur
        dp_cur = [cur + max(sum_left, sum_right)
                  for cur, sum_left, sum_right
                  in zip(triangle_row, dp_prev, dp_prev[1:])]
    return dp_cur[0]