사용자 도구

사이트 도구


ps:problems:boj:1932

정수 삼각형

ps
링크https://www.acmicpc.net/problem/1932
출처BOJ
문제 번호1932
문제명정수 삼각형
레벨실버 1
분류

DP

시간복잡도O(n^2)
인풋사이즈n<=500
사용한 언어Python
제출기록29088KB / 164ms
최고기록112ms
해결날짜2020/11/19

풀이

  • 2차원 DP
  • (i,j) 로 끝나는 경로중 최대값은, 마지막에 대각선 왼쪽에서 내려오는 경로와 대각선 오른쪽에서 내려오는 경로 중 큰 값이다.
    • DP[i][j] = num[i][j] + max(DP[i-1][j-1], DP[i-1][j])

코드

"""Solution code for "BOJ 1932. 정수 삼각형".

- Problem link: https://www.acmicpc.net/problem/1932
- Solution link: http://www.teferi.net/ps/problems/boj/1932
"""

def main():
    n = int(input())
    dp_cur = [0]
    for i in range(n):
        nums = [int(x) for x in input().split()]
        dp_cur, dp_prev = [None] * (i + 1), dp_cur
        dp_cur[0] = dp_prev[0] + nums[0]
        dp_cur[1:i] = [max(dp_prev[j - 1], dp_prev[j]) + nums[j]
                       for j in range(1, i)]
        dp_cur[i] = dp_prev[i - 1] + nums[i]

    print(max(dp_cur))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q V H​ V E
 
ps/problems/boj/1932.txt · 마지막으로 수정됨: 2020/11/28 13:12 저자 teferi