#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
/* <문제해결>
이 문제는 문제 "RGB거리"를 풀어봤다면 쉽게 해결방법을 떠올릴 수 있다.
문제해결방법은 다음과같다.
각 단계(1~N번째 줄)에서 첫번째 숫자를 택했을 때, 두번째 숫자를 택했을 때,
세번째 숫자를 택했을 때 각각의 경우에서 최대 최소값을 구한다.
이때 첫번째 숫자를 택하려면 이전단계에서 첫번째 또는 두번째 숫자를 선택해야하고,
두번째 숫자를 택하려면 이전단계에서 1,2,3번째 숫자중 택해야하고,
세번째 숫자를 택하려면 이전단계에서 2 또는 3번째 숫자를 선택해야한다.
1 2 3
4 5 6
4 9 0
예제입력에서 두번째 줄의 최대값을 구해본다면,
4를 선택했을 때 - 첫번째 줄의 숫자(1, 2) 중 2를 선택하면된다. -> 6
5를 선택했을 때 - 첫번째 줄의 숫자(1, 2, 3) 중 3를 선택하면된다. -> 8
6를 선택했을 때 - 첫번째 줄의 숫자(2, 3) 중 3를 선택하면된다. -> 9
최종적으로는 각 경우에서의 최대값을 출력하면된다.
따라서 점화식으로는
dp[i][1] = max/min(dp[i-1][1], dp[i-1][2]) + arr[i][1];
dp[i][2] = max/min(min/max(dp[i-1][1], dp[i-1][2]), dp[i-1][3]) + arr[i][2];
dp[i][3] = max/min(dp[i-1][2], dp[i-1][3]) + arr[i][3];
가 된다.
하지만 문제는, 사용가능한 메모리가 4MB로, 입력 N이 최대 100,000 이며 int형 배열을
사용한다면 메모리초과가 발생한다.
따라서 모든 입력과 dp값을 저장하지 않고, 각 단계에서마다 처리하고 끝을내야한다.
그렇게되면 순서에따라 다르겠지만 기존의 dp값이 새롭게 덮어씌어지므로 따로 저장해놓아야한다.
*/
int arr[4]; // 입력되는 숫자 3개를 저장할 배열
int temp[3]; // dp[1] dp[2]를 기억해놓기 위한 배열
int min_dp[4];
int max_dp[4];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
// 첫번째 입력처리
cin >> min_dp[1] >> min_dp[2] >> min_dp[3];
// 초기값 설정
max_dp[1] = min_dp[1];
max_dp[2] = min_dp[2];
max_dp[3] = min_dp[3];
// 두번째 ~ N번째 입력 처리
for (int i = 1;i < n;i++)
{
cin >> arr[1] >> arr[2] >> arr[3];
// 이전의 dp값 기억해놓기
temp[1] = max_dp[1];
temp[2] = max_dp[2];
// dp값이 업데이트 됐으므로 temp로 대체
max_dp[1] = max(max_dp[1], max_dp[2]) + arr[1];
max_dp[2] = max(max(temp[1], max_dp[2]), max_dp[3]) + arr[2];
max_dp[3] = max(temp[2], max_dp[3]) + arr[3];
// 이전의 dp값 기억해놓기
temp[1] = min_dp[1];
temp[2] = min_dp[2];
min_dp[1] = min(min_dp[1], min_dp[2]) + arr[1];
min_dp[2] = min(min(temp[1], min_dp[2]), min_dp[3]) + arr[2];
min_dp[3] = min(temp[2], min_dp[3]) + arr[3];
}
cout << max(max(max_dp[1], max_dp[2]), max_dp[3]) << " ";
cout << min(min(min_dp[1], min_dp[2]), min_dp[3]);
}
댓글남기기