[백준 BOJ_2096] 내려가기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀어주었습니다.

처음에는 3차원 배열로 내려가며 각각 max와 min을 갱신하여 구해주었지만 메모리 초과가 나게 되었습니다. 그래서 한 줄씩 입력받아 cache를 갱신해주며 풀어주었습니다. cache는 다음과 같습니다.

i = 0 or 1 or 2
max_cache[i] = i번째 숫자를 골랐을 때의 최대합
min_cache[i] = i번째 숫자를 골랐을 때의 최소합

각각의 위치의 숫자를 골랐을 때 비교해줄 수 있는 숫자들은 다음과 같습니다.

• 첫 번째 숫자: cache[0], cache[1]
• 두 번째 숫자: cache의 모든 숫자
• 세 번째 숫자: cache[1], cache[2]

해당 숫자 중에 가장 큰, 그리고 가장 작은 값을 가지는 숫자를 현재 위치의 숫자에 더해준 값을 따로 저장해준 뒤, 마지막에 cache를 갱신해줍니다.

마지막에는 max_cache의 최댓값과 min_cache의 최솟값을 구해 출력해줍니다.

코드

import sys

input = sys.stdin.readline

N = int(input())

max_cache = list(map(int, input().split()))
min_cache = max_cache[:]
for _ in range(N-1):
  a, b, c = map(int, input().split())
  max_a = a + max(max_cache[0], max_cache[1])
  min_a = a + min(min_cache[0], min_cache[1])

  max_b = b + max(max_cache)
  min_b = b + min(min_cache)

  max_c = c + max(max_cache[1], max_cache[2])
  min_c = c + min(min_cache[1], min_cache[2])
  
  max_cache[0] = max_a
  min_cache[0] = min_a

  max_cache[1] = max_b
  min_cache[1] = min_b

  max_cache[2] = max_c
  min_cache[2] = min_c

print(max(max_cache), min(min_cache))