dp를 활용한 문제이다. 다음 줄의 인접한 인덱스로 내려가면서 더한 최대 점수와 최소 점수를 구하면 된다. tmp
와 dp
두 배열을 이용하여 문제를 해결했다. 처음 dp
배열에 A
배열의 첫 줄을 저장하고 maxSum
함수에 들어간다. 함수 내에서 tmp
배열에 dp
와 A
의 합의 최댓값을 구하여 저장하고 tmp
와 스왑을 해준다. 이를 반복하면 중간 과정을 모두 저장할 필요 없이 최댓값을 구할 수 있따. minSum
또한 같은 방식으로 진행된다. 다만 minSum
인 경우, 0이 있으면 이전의 값을 무시하고 0을 저장하므로 0인 경우와 아닌 경우로 분리해주었다.
처음에는 중간 과정을 모두 저장하여 메모리 초과가 발생했었다. 배열 두개를 사용하여 쉽게 해결할 수 있었다.
#include <iostream>
#include <algorithm>
using namespace std;
int N, mmax = 0, mmin = 987654321;
int A[100001][3];
int tmp[3];
int dp[3];
void maxSum() {
for (int i = 1; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j == 0 && k == 2) continue;
if (j == 2 && k == 0) continue;
tmp[j] = max(tmp[j], dp[k] + A[i][j]);
}
}
swap(dp, tmp);
for (int j = 0; j < 3; j++) {
tmp[j] = 0;
}
}
for (int i = 0; i < 3; i++) {
mmax = max(mmax, dp[i]);
}
}
void minSum() {
for (int i = 1; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j == 0 && k == 2) continue;
if (j == 2 && k == 0) continue;
if (tmp[j] != 0) {
tmp[j] = min(tmp[j], dp[k] + A[i][j]);
}
else {
tmp[j] = dp[k] + A[i][j];
}
}
}
swap(dp, tmp);
for (int j = 0; j < 3; j++) {
tmp[j] = 0;
}
}
for (int i = 0; i < 3; i++) {
mmin = min(mmin, dp[i]);
}
}
void solution() {
for (int i = 0; i < 3; i++) {
dp[i] = A[0][i];
}
maxSum();
for (int i = 0; i < 3; i++) {
dp[i] = A[0][i];
}
minSum();
cout << mmax << " " << mmin;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}