1 minute read

문제

접근 방법

이전 row에 저장된 값을 통해 현재 row의 최대값, 최소값을 구하는 문제이므로 DP와 memoization을 활용하는 문제임을 알 수 있다. 하지만 여기서 문제점은 메모리 제한이 4MB이라는 것이다.

정석대로 DP memoization을 한다면 3개의 칸, n개의 행을 가진 두 개의 테이블에 각각 최대와 최소값을 저장해야 한다. 하지만 이렇게 되면 2 x 3 x n x 8 bytes = 4.8 MB를 소요하게 된다.

따라서 memoization을 직전 값에 대해서만 고려하면 된다는 것을 통해 해결하였다.

정답 코드


import sys
input = sys.stdin.readline

'''
메모리 제한이 빡세다. 줄 하나씩 내려가면서 각 칸이 가질 수 있는 최대값만 저장하면서 내려가면서 풀면 3*100000*8 byte -> 2.4 mb이다. 이것을 최솟값에 대해서도 반복을 하면 4.8mb로 메모리 제한에 걸린다.

따라서 전체를 저장하지 말고 한 줄씩만 처리하면 된다.
'''

n = int(input())
max_val = 0
min_val = 0


# 이전 값들을 저장
oldmax_1, oldmax_2, oldmax_3 = map(int, input().split())
oldmin_1, oldmin_2, oldmin_3 = oldmax_1, oldmax_2, oldmax_3
for _ in range(n-1):
  # 현재 값들을 가져와 이를 이전값과 더해서 최대값 구함
  new_1, new_2, new_3 = map(int, input().split())
  newmax_1 = new_1 + max(oldmax_1, oldmax_2)
  newmax_2 = new_2 + max(oldmax_1, oldmax_2, oldmax_3)
  newmax_3 = new_3 + max(oldmax_2, oldmax_3)

  newmin_1 = new_1 + min(oldmin_1, oldmin_2)
  newmin_2 = new_2 + min(oldmin_1, oldmin_2, oldmin_3)
  newmin_3 = new_3 + min(oldmin_2, oldmin_3)
  
  oldmax_1, oldmax_2, oldmax_3 = newmax_1, newmax_2, newmax_3
  oldmin_1, oldmin_2, oldmin_3 = newmin_1, newmin_2, newmin_3

  
max_val = max(oldmax_1, oldmax_2, oldmax_3)
min_val = min(oldmin_1, oldmin_2, oldmin_3)

print(f"{max_val} {min_val}")

You May Also Enjoy