내려가기

• 내려가기 2의 어려운 버전. 인풋은 모두 동일하지만, 메모리 제한이 걸려있다.
• O(n) 시간복잡도의 DP로 푸는 것은 동일하지만, 내려가기 2는 O(n)의 dp 테이블을 만들어서 푸는 것이 가능했지만, 여기에서는 반드시 슬라이딩 윈도우 테크닉을 사용해서 공간 복잡도를 O(1)으로 만들어야 한다.

"""Solution code for "BOJ 2096. 내려가기".

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

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