171025_2096_내려가기

#include <iostream> using namespace std; int max(int a, int b) {return a > b ? a : b;} int max(int a, int b, int c) {return max(a, b) > c ? max(a, b) : c;} int min(int a, int b) {return a < b ? a : b;} int min(int a, int b, int c) {return min(a, b) < c ? min(a, b) : c;} int main() { int N; cin >> N; int max_arr[2][3] = { 0 }; int min_arr[2][3] = { 0 }; int input[3] = { 0 }; for (int i = 1; i <= N; i++) { cin >> input[0] >> input[1] >> input[2]; max_arr[2][0] = max(max_arr[1][0], max_arr[1][1]) + input[0]; min_arr[2][0] = min(min_arr[1][0], min_arr[1][1]) + input[0]; max_arr[2][1] = max(max_arr[1][0], max_arr[1][1], max_arr[1][2]) + input[1]; min_arr[2][1] = min(min_arr[1][0], min_arr[1][1], min_arr[1][2]) + input[1];                 max_arr[2][2] = max(max_arr[1][1], max_arr[1][2]) + input[2]; min_arr[2][2] = min(min_arr[1][1], min_arr[1][2]) + input[2]; for (int j = 0; j<3; j++) { max_arr[1][j] = max_arr[2][j]; min_arr[1][j] = min_arr[2][j]; } } cout << max(max_arr[2][0], max_arr[2][1], max_arr[2][2]) << " " << min(min_arr[2][0], min_arr[2][1], min_arr[2][2]); }

dp배열을 100001개씩 만들면 메모리 초과가 떠서 2*3 배열 2개로 각각의 위치에서의 min, max값 저장

값을 이동시켜서 반복