내려가기 2

• 기초적인 DP 문제.
• 3*N 크기의 dp 테이블을 채워 나가면 된다. 시간 복잡도는 O(n)
• 슬라이딩 윈도우 기법을 적용하는 것도 가능하고 아래 코드도 그렇게 작성된 코드이지만, 이 문제에서는 굳이 안쓰더라도 상관은 없다. 슬라이딩 윈도우를 반드시 사용해야만 풀리도록 만든 문제는 내려가기이다.

"""Solution code for "BOJ 15645. 내려가기 2".

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

Tags: [DP]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    min_l = min_m = min_r = max_l = max_m = max_r = 0
    for _ in range(N):
        l, m, r = [int(x) for x in sys.stdin.readline().split()]
        min_l, min_m, min_r = (min(min_l, min_m) + l,
                               min(min_l, min_m, min_r) + m,
                               min(min_m, min_r) + r)
        max_l, max_m, max_r = (max(max_l, max_m) + l,
                               max(max_l, max_m, max_r) + m,
                               max(max_m, max_r) + r)

    print(max(max_l, max_m, max_r), min(min_l, min_m, min_r))


if __name__ == '__main__':
    main()