문제
풀이
다이나믹 프로그래밍 문제이다.
처음에는 dp 2차원 배열을 n행 3열 만큼 할당하여 풀었는데, 메모리 초과가 나왔다.
메모리 초과를 해결하기 위해 n행 3열 만큼 배열을 할당하는 것이 아니라, 최대 값을 저장하는 dp 배열과, 최소 값을 저장하는 dp 배열을 2행 3열 크기로 할당하여 풀었다.
1
2
int maxWindow[2][3];
int minWindow[2][3];
maxWindow 배열과, minWindow 배열을 n행의 원본 배열에서 윈도우 슬라이딩 형식으로 내려가며 dp를 수행해주면 메모리 초과를 피할 수 있다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int map[100001][3];
int maxWindow[2][3];
int minWindow[2][3];
void input()
{
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 >> map[i][j];
}
}
}
void solve()
{
for (int i = 0; i < 3; i++)
maxWindow[0][i] = minWindow[0][i] = map[0][i];
for (int i = 1; i < n; i++)
{
maxWindow[1][0] = map[i][0] + max(maxWindow[0][0], maxWindow[0][1]);
maxWindow[1][1] = map[i][1] + max(maxWindow[0][0], max(maxWindow[0][1], maxWindow[0][2]));
maxWindow[1][2] = map[i][2] + max(maxWindow[0][2], maxWindow[0][1]);
minWindow[1][0] = map[i][0] + min(minWindow[0][0], minWindow[0][1]);
minWindow[1][1] = map[i][1] + min(minWindow[0][0], min(minWindow[0][1], minWindow[0][2]));
minWindow[1][2] = map[i][2] + min(minWindow[0][2], minWindow[0][1]);
for (int j = 0; j < 3; j++)
{
maxWindow[0][j] = maxWindow[1][j];
minWindow[0][j] = minWindow[1][j];
}
}
int min_res = min(minWindow[0][0], min(minWindow[0][1], minWindow[0][2]));
int max_res = max(maxWindow[0][0], max(maxWindow[0][1], maxWindow[0][2]));
cout << max_res << ' ' << min_res;
}
int main()
{
input();
solve();
return 0;
}
