https://www.acmicpc.net/problem/2096
시간 1초, 메모리 4MB
input :
- N(1 ≤ N ≤ 100,000)
- N개의 줄에는 숫자가 세 개씩
output :
- 최대 점수와 최소 점수를 띄어서 출력
조건 :
-
-
위와 같이 움직일 수 있다.
각 위치에 올 수 있는 최댓값, 그리고 최솟값을 찾아서 각 배열의 값을 업데이트 하자.
dpmax = max(dpmax[0], dpmax[1]) + data[i][0], max(dpmax) + data[i][1], max(dpmax[1], dpmax[2]) + data[i][2]
dpmin = min(dpmin[0], dpmin[1]) + data[i][0], min(dpmin) + data[i][1], min(dpmin[1], dpmin[2]) + data[i][2]위치가 0 : 0, 1 둘 중 max + data[i][0] (0번 째 위치의 값)
위치가 1 : 0, 1, 2 중 max + data[i][1] (1번 째 위치의 값)
위치가 2 : 1, 2 중 max + data[i][2] (2번 째 위치의 값)
길이가 3으로 고정이기 떄문에 그냥 이 3가지 경우를 다 따지자.
그리고 이 메모리 조건이 매우 작기 때문에 dp의 크기 자체가 적어야 한다.
이럴 때는 1차원 배열을 계속 업데이트 하는 방식을 사용하도록 하자.
import sys
n = int(sys.stdin.readline())
data = []
for i in range(n):
data.append(list(map(int, sys.stdin.readline().split())))
dpmax = [data[0][0], data[0][1], data[0][2]]
dpmin = [data[0][0], data[0][1], data[0][2]]
for i in range(1, n):
dpmax = max(dpmax[0], dpmax[1]) + data[i][0], max(dpmax) + data[i][1], max(dpmax[1], dpmax[2]) + data[i][2]
dpmin = min(dpmin[0], dpmin[1]) + data[i][0], min(dpmin) + data[i][1], min(dpmin[1], dpmin[2]) + data[i][2]
print(max(dpmax), min(dpmin))
