[백준] 내려가기

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

2096번: 내려가기

다이나믹 프로그래밍을 이용하여 푸는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

1	2	3
4	5	6
7	8	9
9	7	1

위의 그림과 같이 array가 주어집니다. 이때, 가장 위에서 원룡이가 내려가게 되는데, 바로 아래방향에 있는 수로 넘어가거나, 그 수와 붙어있는 수로만 이동할 수 있다는 조건이 있습니다. 이때, 가장 아래까지 도달했을 때, 얻을 수 있는 최대 점수와 최소 점수를 return 해야 합니다.

 

<Solution>

문제의 메모리 제한이 4MB로 크지 않으므로, dp table을 전체에 대해 만들어주지 않고, 필요한 부분에만 만들어 주었습니다. (이전에 계산한 정보만 필요함)

알고리즘은 다음과 같습니다. 특정한 행(i)까지의 최댓값을 구하고 싶으면, 그 전 행(i-1) 까지의 최댓값을 구한 dp_array를 활용하여, dp_array를 다시 구성하는 형태입니다. 

 

최솟값의 경우에도 동일하게 진행하면 됩니다.

 

실제 구현은 다음과 같습니다. 

import sys
import copy
N = int(sys.stdin.readline().rstrip())

i, j, k = list(map(int,sys.stdin.readline().rstrip().split()))
array_max = [i,j,k]
array_min = [i,j,k]

for _ in range(N-1):
    i, j, k = list(map(int,sys.stdin.readline().rstrip().split()))
    # for max
    array_max_ = copy.deepcopy(array_max)
    array_max[0] = max(array_max_[0]+i, array_max_[1]+i)
    array_max[1] = max(array_max_[0]+j, array_max_[1]+j, array_max_[2]+j)
    array_max[2] = max(array_max_[1]+k, array_max_[2]+k)
    # for min
    array_min_ = copy.deepcopy(array_min)
    array_min[0] = min(array_min_[0]+i, array_min_[1]+i)
    array_min[1] = min(array_min_[0]+j, array_min_[1]+j, array_min_[2]+j)
    array_min[2] = min(array_min_[1]+k, array_min_[2]+k)

print(str(max(array_max))+' '+str(min(array_min)))