생각해야할 부분
- 메모리 제한이 4MB이다.
보통 문제 풀때 시간 제한만 보고 알고리즘을 구상하다보니 첫 제출에서 메모리 초과가 났다. ㅜ.ㅜ
dp 문제라 메모라이즈하려는 생각에 간과한 메모리초과라고 할 수 있다.
첫 풀이에서는 vector을 써서 n만큼 입력 벡터와 dp 벡터를 할당해 주었다. 사실 이도 십만 x 3 x 2 x 4바이트(int)라 얼추 가능할거라 생각했다.
But c++ 자체에서 1-2MB 사용하고 iostream 사용시 기본 2MB 사용한다고 한다.. 그러면 절대 안되지..
알고나면 간단한 문제이고 더 좋은 코드를 쓰기 위해 중요한 부분인거 같다.
정답 풀이
#include<iostream>
#include<algorithm>
using namespace std;
pair<int, int> dp[3][3];
int n;
void getValue(int []);
int main() {
cin >> n;
int arr[3];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
int temp;
cin >> temp;
arr[j] = temp;
}
if (i == 0) {
dp[0][0]=make_pair(arr[0], arr[0]);
dp[0][1]=make_pair(arr[1], arr[1]);
dp[0][2]=make_pair(arr[2], arr[2]);
}else getValue(arr);
}
cout << max({ dp[0][0].second, dp[0][1].second, dp[0][2].second }) << " " << min({ dp[0][0].first, dp[0][1].first, dp[0][2].first });
return 0;
}
void getValue(int a[]) {
int minV;
int maxV;
minV= min(dp[0][0].first, dp[0][1].first)+a[0];
maxV= max(dp[0][0].second, dp[0][1].second)+a[0];
dp[1][0]=make_pair(minV, maxV);
minV = min({ dp[0][0].first, dp[0][1].first ,dp[0][2].first})+a[1];
maxV= max({ dp[0][0].second, dp[0][1].second ,dp[0][2].second })+a[1];
dp[1][1]=make_pair(minV, maxV);
minV= min(dp[0][1].first, dp[0][2].first)+a[2];
maxV= max(dp[0][1].second, dp[0][2].second)+a[2];
dp[1][2]=make_pair(minV, maxV);
swap(dp[0], dp[1]);
}