사용자 도구

사이트 도구


ps:problems:programmers:43105

정수 삼각형

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호43105
문제명정수 삼각형
레벨Level 3
분류

동적 계획법

시간복잡도O(n^2)
인풋사이즈n<=500
사용한 언어Python
해결날짜2021/06/25
태그

고득점 Kit - 동적계획법

풀이

  • 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)까지 가는 경로를 찾는 식으로 계산하면 좀 더 코드가 깔끔해진다. 두가지 코드를 다 첨부했다

코드

코드 1 - 꼭짓점에서 아래로 내려오는 경로를 계산

"""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)

코드 2 - 바닥에서 위로 올라가는 경로를 계산

"""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]

토론

댓글을 입력하세요:
K F J G Y
 
ps/problems/programmers/43105.txt · 마지막으로 수정됨: 2021/06/29 12:56 저자 teferi