[Python] BOJ 2096 - 내려가기

https://www.acmicpc.net/problem/2096

2096번: 내려가기

# 처음에 그냥 숫자 3개씩 N줄을 m에 다 입력받고 풀었는데 메모리 초과가 났다.

 

# 메모리제한이 4MB로 매우 작다. 따라서 dp배열도 N줄으로 만들면 안되고 3칸씩 2줄을 선언해서

   계속 반복해주어야 한다.

   입력되는 숫자들 역시 한번에 입력받으면 안되고 dp테이블을 갱신해줄때마다 한줄씩 입력받아

   그때그때 처리를 해줘야 한다.

 

# 최대점수, 최소점수를 구해야 하므로 min_dp, max_dp 배열 두개를 사용하였다.

   dp[1][0]은 위에서 내려오는 경우(dp[0][0])와 오른쪽 위에서 내려오는 경우(dp[0][1])에

                   m[0]를 더한값 중 최솟값

   dp[1][1]은 dp[0][0], dp[0][1], dp[0][2]에 m[1]을 더한값 중 최솟값

   dp[1][2]는 dp[0][1], dp[0][2]에 m[2]를 더한값 중 최솟값을 넣어준다.

 

# 그리고 dp[1][0], dp[1][1], dp[1][2]를 각각 dp[0][0], dp[0][1], dp[0][2]에 넣어준다.

   어차피 맨 아래줄에서의 최대점수와 최소점수를 구해야 하므로 이전의 구한 값들은

   저장안해도 상관없다.

 

# N줄을 내려온 뒤, max_dp[0]의 최댓값과 min_dp[0]의 최솟값을 출력한다.

 

import sys
input = sys.stdin.readline
N = int(input())
min_dp = [[0] * 3 for _ in range(2)]
max_dp = [[0] * 3 for _ in range(2)]

for i in range(N):
	m = list(map(int,input().split()))
	min_dp[1][0] = min(min_dp[0][0] + m[0], min_dp[0][1] + m[0])
	max_dp[1][0] = max(max_dp[0][0] + m[0], max_dp[0][1] + m[0])

	min_dp[1][1] = min(min_dp[0][0] + m[1], min_dp[0][1] + m[1], min_dp[0][2] + m[1])
	max_dp[1][1] = max(max_dp[0][0] + m[1], max_dp[0][1] + m[1], max_dp[0][2] + m[1])

	min_dp[1][2] = min(min_dp[0][1] + m[2], min_dp[0][2] + m[2])
	max_dp[1][2] = max(max_dp[0][1] + m[2], max_dp[0][2] + m[2])

	for j in range(3):
		min_dp[0][j] = min_dp[1][j]
		max_dp[0][j] = max_dp[1][j]

print(max(max_dp[0]), min(min_dp[0]))