[백준] 2096번 내려가기 (C++)

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

문제 설명

n개의 줄에 세 개의 숫자가 주어진다. 

(i,j)가 이동할 수 있는 경로는 (i+1,j-1) 또는 (i+1,j) 또는 (i+1,j+1)로만 가능하다. 

첫 줄에서부터 마지막 줄로 이동할 때 얻을 수 있는 최대 점수와 최저 점수를 구하는 문제이

 

주요 로직

1. dp문제이다
2. 메모리가 4MB이기 때문에 모든 입력을 다 받고 나서 계산하는 것보다는 입력값 한줄을 받고 나서 그 때 그때 계산해야 한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,tmp1, tmp2;
int input[4], mn[4], mx[4];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	cin >> mx[0] >> mx[1] >> mx[2];
	mn[0] = mx[0], mn[1] = mx[1], mn[2] = mx[2];
	
	for(int i=1; i<n; i++){
		cin >> input[0] >> input[1] >> input[2];
		
		tmp1 = mn[0], tmp2 = mn[2];
		mn[0] = min(mn[0], mn[1]) + input[0];
		mn[2] = min(mn[1], mn[2]) + input[2];
		mn[1] = min(min(tmp1, mn[1]), tmp2) + input[1];
		
		tmp1 = mx[0], tmp2 = mx[2];
		mx[0] = max(mx[0], mx[1]) + input[0];
		mx[2] = max(mx[1], mx[2]) + input[2];
		mx[1] = max(max(tmp1, mx[1]), tmp2) + input[1];
	}
	
	cout << max(max(mx[1], mx[2]), mx[0]) << " ";
	cout << min(min(mn[1], mn[2]), mn[0]) << "\n";
	
	return 0;
}