'알고리즘' 카테고리의 다른 글
| [DP] 백준 10942 팰린드롬? (0) | 2018.04.29 |
|---|---|
| [DP] 백준 1890 점프, 3372 보드 점프 다시풀만한 것 (0) | 2018.04.29 |
| [DP] 백준 9507 Generations of Tribbles (0) | 2018.04.29 |
| [DP] 백준 1309 동물원 (0) | 2018.04.29 |
| [DP] 백준 2225 합분해 (개수가 주어진 문제) (0) | 2018.04.29 |
[DP] 백준 2096 내려가기
2018. 4. 29. 00:32
Top-down 구현.
문제에서 메모리 제한이 4MB
메모리 초과가 나서 이 문제에선 사용할 수 없다.
최대로 더해가는 DP와 최소로 더해가는 DP를 보려면 이 코드를 보면 될 것 같다.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tb[100001][3];
int che[100001][3];
int n;
int go(int line, int loca) {
if (line == n) {
return 0;
}
if (che[line][loca] != -1) {
return che[line][loca];
}
int& ret = che[line][loca] = tb[line][loca];
if (loca == 0) {
for (int i = 0; i < 2; ++i) {
ret = max(ret, go(line + 1, i) + tb[line][loca]);
}
}
if (loca == 1) {
for (int i = 0; i < 3; ++i) {
ret = max(ret, go(line + 1, i) + tb[line][loca]);
}
}
if (loca == 2) {
for (int i = 1; i < 3; ++i) {
ret = max(ret, go(line + 1, i) + tb[line][loca]);
}
}
return ret;
}
int go2(int line, int loca) {
if (line == n) {
return 0;
}
if (che[line][loca] != -1) {
return che[line][loca];
}
int& ret = che[line][loca] = tb[line][loca];
//cout << ret << '\n';
if (loca == 0) {
for (int i = 0; i < 2; ++i) {
ret =go2(line + 1, i) + tb[line][loca];
}
}
if (loca == 1) {
for (int i = 0; i < 3; ++i) {
ret = go2(line + 1, i) + tb[line][loca];
}
}
if (loca == 2) {
for (int i = 1; i < 3; ++i) {
ret = go2(line + 1, i) + tb[line][loca];
}
}
return ret;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(che, -1, sizeof(che));
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> tb[i][j];
}
}
int ans = -1;
for (int i = 0; i < 3; ++i) {
ans = max(ans, go(0, i));
}
cout << ans << ' ';
memset(che, -1, sizeof(che));
ans = INT32_MAX;
for (int i = 0; i < 3; ++i) {
ans = min(ans, go2(0, i));
}
/*
for debugging
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
cout << mche[i][j] << ' ';
}
cout << '\n';
}*/
cout << ans << endl;
return 0;
}
bottom up 방식으로 해서 모든 결과를 저장해두지 않고 필요한 만큼 저장해 두었다.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int n;
int tb[3];
int che[3][3];
int mche[3][3];
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < 3; ++i) {
che[1][i] = -1;
mche[1][i] = INT32_MAX;
}
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> tb[j];
}
if (i == 0) {
for (int k = 0; k < 3; ++k) {
che[i][k] = tb[k];
mche[i][k] = tb[k];
}
}
else {
for (int k = 0; k < 2; ++k) {
che[1][0] = max(che[1][0], che[0][k] + tb[0]);
mche[1][0] = min(mche[1][0],mche[0][k] + tb[0]);
}
for (int k = 0; k < 3; ++k) {
che[1][1] = max(che[1][1], che[0][k] + tb[1]);
mche[1][1] = min(mche[1][1], mche[0][k] + tb[1]);
}
for (int k = 1; k < 3; ++k) {
che[1][2] = max(che[1][2], che[0][k] + tb[2]);
mche[1][2] = min(mche[1][2], mche[0][k] + tb[2]);
}
for (int k = 0; k < 3; ++k) {
che[0][k] = che[1][k];
mche[0][k] = mche[1][k];
che[1][k] = -1;
mche[1][k] = INT32_MAX;
}
}
}
int ans = 0;
for (int i = 0; i < 3; ++i) {
ans = max(ans, che[0][i]);
}
cout << ans << ' ';
ans = INT32_MAX;
for (int i = 0; i < 3; ++i) {
ans = min(ans, mche[0][i]);
}
cout << ans << endl;
return 0;
}