[알고리즘][Python] 백준 2096 내려가기 문제 풀이

문제 출처 : www.acmicpc.net/problem/2096

2096번: 내려가기

---

문제 해석 : 3칸으로 이루어진 배열에서 각 배열을 자신의 바로 아래 혹은 그와 붙어있는 칸으로 움직일 수 있다. 이때 마지막까지 갔을 때 최소, 최대 값을 구하세요

 

문제 풀이 : 메모리 제한이 빡빡하기 때문에 슬라이딩 윈도우와 다이나믹 프로그래밍을 이용해서 문제를 풀어야 한다.

-> 모든 순간을 저장하는 배열이 아닌 필요한 만큼만 이동하면서 계산을 진행해야 한다.

---

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = []
arr_max = [[0,0,0],[0,0,0]]
arr_min = [[0,0,0],[0,0,0]]

for _ in range(N):
    A,B,C = list(map(int, input().split()))
    arr.append([A,B,C])

for i in range(0,N):

    arr_max[1][0] = max(arr_max[0][1], arr_max[0][0]) + arr[i][0]
    arr_max[1][1] = max(arr_max[0][1], arr_max[0][2], arr_max[0][0]) + arr[i][1]
    arr_max[1][2] = max(arr_max[0][1], arr_max[0][2]) + arr[i][2]

    arr_min[1][0] = min(arr_min[0][0], arr_min[0][1]) + arr[i][0]
    arr_min[1][1] = min(arr_min[0][1], arr_min[0][2], arr_min[0][0]) + arr[i][1]
    arr_min[1][2] = min(arr_min[0][1], arr_min[0][2]) + arr[i][2]

    arr_max.append(arr_max.pop(0))
    arr_min.append(arr_min.pop(0))

print(max(arr_max[0]), end=" ")
print(min(arr_min[0]))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.