[BOJ/백준] 2096 내려가기

import sys

input = sys.stdin.readline

N = int(input())

arr =[ list(map(int,input().split())) for _ in range(N)]

max_arr = [[0]*3 for _ in range(2)]
min_arr = [[0]*3 for _ in range(2)]

max_arr[0][0] = min_arr[0][0] = arr[0][0]
max_arr[0][1] = min_arr[0][1] = arr[0][1]
max_arr[0][2] = min_arr[0][2] = arr[0][2]

for i in range(1,N):
    max_arr[1][0] = arr[i][0] + max(max_arr[0][0],max_arr[0][1])
    max_arr[1][1] = arr[i][1] + max(max_arr[0][0],max_arr[0][1],max_arr[0][2])
    max_arr[1][2] = arr[i][2] + max(max_arr[0][1],max_arr[0][2])
    min_arr[1][0] = arr[i][0] + min(min_arr[0][0],min_arr[0][1])
    min_arr[1][1] = arr[i][1] + min(min_arr[0][0],min_arr[0][1],min_arr[0][2])
    min_arr[1][2] = arr[i][2] + min(min_arr[0][1],min_arr[0][2])

    for y in range(3):
        max_arr[0][y] = max_arr[1][y]
        min_arr[0][y] = min_arr[1][y]

print(max(max_arr[0]),min(min_arr[0]))

처음 풀어본 슬라이딩 윈도우 관련 문제이다. 들어오는 N의 최대값이 10만이므로, 그대로 전체에 대해서 행렬을 만들경우, 메모리 초과가 날 수 있다.

 

그럴때 사용하는 알고리즘인 것 같다.

 

슬라이딩 윈도우에 관련된 설명은 blog.fakecoding.com/archives/algorithm-slidingwindow/ 에서 공부했다.

 

이 문제도 슬라이딩 윈도우를 통해, 최대값과 최소값을 갱신해주면 되는 문제이다.

 

일단 한 행에는 3개의 인수가 나와있고, 그 행에서 최대값을 얻을 수 있는 경우는

 

첫번째 열은 첫번째 열과 값과 그전 행의 첫번째 열과 두번째 열 중 더 큰 값을 더하는 경우이고,

두번째 열은 두번째 열의 값과 그전 행의 첫번째, 두번째, 세번째 열 중  가장 큰 값과 더해주는 것이다.

세번째 열은 세번째 열의 값과 그전 행의 두번쨰,세번째 열 중 가장 큰 값과 더해주는 것이다.

 

구해진 값들은 현재 행의 각 열에서의 최대값을 구한것이다. 그러면 이 다음행은 이 전전 행 현재행의 그전 행의 값의 유무는 상관이 없다. 현재행의 값들만 알고 있으면 위의 로직을 다음행에서 진행할때에는 전전행은 필요가 없으므로, 현재행에서 구한 값들의 위치를 이전행으로 옮겨주는 과정을 하면 된다.

 

최소값은 max에서 min으로 바꿔주기만 하면 된다.