문제 : https://www.acmicpc.net/problem/2096
[ 알고리즘풀이 ]
이 문제는 전형적인 쉬운 2차원 DP 문제이나, 4MB 라는 메모리 제한 때문에 배열 선언에 제약이 걸려있는 문제입니다. 따라서, 2행 3열짜리 2차원 배열을 선언해서 첫 번째 행에는 현재까지 가장 큰 값, 가장 작은 값을 저장하고 두 번째 행에는 들어온 입력값과 첫 번째 행의 값을 이용해 새롭게 가장 큰 값, 가장 작은 값은 갱신해줍니다. 그 후, 두 번째 행을 첫 번째 행에 덮어가며 N행 3열 2차원 배열이 아닌 2행 3열 2차원 배열로 문제를 해결할 수 있습니다.
ansMap[0][j].first : 현재까지 j번 째 열에서 얻을 수 있는 가장 큰 값
ansMap[0][j].second : 현재까지 j번 째 열에서 얻을 수 있는 가장 작은 값
#include<iostream>
#include<algorithm>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, map[3] = {};
pair<int, int> ansMap[2][3] = {};
cin >> N;
cin >> map[0] >> map[1] >> map[2];
for (int j = 0; j < 3; j++) {
ansMap[0][j].first = ansMap[0][j].second = map[j];
}
for (int i = 1; i < N; i++) {
cin >> map[0] >> map[1] >> map[2];
ansMap[1][0].first = max(ansMap[0][0].first, ansMap[0][1].first) + map[0];
ansMap[1][0].second = min(ansMap[0][0].second, ansMap[0][1].second) + map[0];
ansMap[1][1].first = max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) + map[1];
ansMap[1][1].second = min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second }) + map[1];
ansMap[1][2].first = max(ansMap[0][1].first, ansMap[0][2].first) + map[2];
ansMap[1][2].second = min(ansMap[0][1].second, ansMap[0][2].second) + map[2];
for (int j = 0; j < 3; j++)
ansMap[0][j].first = ansMap[1][j].first, ansMap[0][j].second = ansMap[1][j].second;
}
cout << max({ ansMap[0][0].first, ansMap[0][1].first, ansMap[0][2].first }) << ' ' << min({ ansMap[0][0].second, ansMap[0][1].second, ansMap[0][2].second });
}
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 16434 : 드래곤 앤 던전 - travelbeeee (0) | 2020.03.17 |
---|---|
[BOJ] 15665 : N과 M(11) - travelbeeee (0) | 2020.03.17 |
[BOJ] 11003 : 최솟값 찾기 - travelbeeee (0) | 2020.03.17 |
[BOJ] 8120 : Coding of Permutations - travelbeeee (0) | 2020.03.16 |
[BOJ] 16637 : 괄호 추가하기 - travelbeeee (0) | 2020.03.13 |