[백준] 2096. 내려가기

문제 링크: https://www.acmicpc.net/problem/2096

2096번: 내려가기

✍🏻코드

import sys

n = int(sys.stdin.readline().rstrip())

max_arr = [0]*3
min_arr = [0]*3
      
max_buf = [0]*3
min_buf = [0]*3

for y in range(n):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    for i in range(3):
        if i == 0:
            max_arr[i] = a + max(max_buf[i],max_buf[i+1])
            min_arr[i] = a + min(min_buf[i], min_buf[i + 1])
        elif i == 1:
            max_arr[i] = b + max(max_buf[i],max_buf[i+1],max_buf[i-1])
            min_arr[i] = b + min(min_buf[i], min_buf[i + 1], min_buf[i - 1])
        else:
            max_arr[i] = c + max(max_buf[i],max_buf[i-1])
            min_arr[i] = c + min(min_buf[i], min_buf[i - 1])
    for j in range(3):
        max_buf[j] = max_arr[j]
        min_buf[j] = min_arr[j]

print(max(max_arr),min(min_arr))

💡풀이

---

• n의 길이만큼 누적합을 계산하게 되면 메모리 초과가 발생한다.
• 같은 배열에 누적합을 갱신하는 방식으로 문제를 해결해야한다.
• 값을 갱신할때, 누적합을 넣는 배열과 max(),min()을 이용해서 비교할 경우, 이전에 갱신된 값과 비교되어 값이 잘못 나온다.
• 그래서 바로 전의 행을 저장해두고 그 행에서 최소,최대값을 비교해서 누적합을 구해야한다.