사용자 도구

사이트 도구


ps:problems:boj:1932

정수 삼각형

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

DP

시간복잡도O(n^2)
인풋사이즈n<=500
사용한 언어Python
제출기록33304KB / 144ms
최고기록112ms
해결날짜2021/06/29

풀이

  • 1994년 IOI 문제. 프로그래머즈의 정수 삼각형도 동일한 문제이다. 풀이는 그쪽 참고.

코드

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

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

Tags: [DP]
"""


def main():
    n = int(input())
    triangle = [[int(x) for x in input().split()] for _ in range(n)]

    dp_cur = [0] * (n + 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:])]
    print(dp_cur[0])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E O​ F A J
 
ps/problems/boj/1932.txt · 마지막으로 수정됨: 2021/06/29 12:58 저자 teferi