Problem link: https://www.acmicpc.net/problem/1983
일단 문제를 보고 2시간 동안 별다른 아이디어가 떠오르지 않아서 답을 보고 풀었다.
답을 보고 풀어낸 것은 차치하더라도 코너 케이스를 찾는 것에 계속 실패해서 꽤나 고전했다.
문제를 풀기 위한 캐시의 정의는 아래와 같다.
CACHE[k][i][j]:k번 열까지A[0] ~ A[i],B[0] ~ B[j]의 수를 배치할 때 곱의 최대 값
이제 CACHE[k][i][j]를 구할 때 k번째 열에 어떤 숫자가 배치될지를 생각해보면, 아래 4가지 경우 중 하나임을 알 수 있다.
Case 1) k번째 열에 모두 0이 오는 경우
| K | ... | k-1 | k |
|---|---|---|---|
| A | ... | ... | 0 |
| B | ... | ... | 0 |
0 ~ k-1열에A[0] ~ A[i],B[0] ~ B[j]가 모두 배치가 끝난 상황으로 이해하면 된다.- 이 경우
CACHE[k][i][j]의 값은CACHE[k-1][i][j] + 0*0과 같을 것이다.
Case 2) k번째 열에 A[i], 0이 오는 경우
| K | ... | k-1 | k |
|---|---|---|---|
| A | ... | ... | A[i] |
| B | ... | ... | 0 |
0 ~ k-1열에A[0] ~ A[i-1],B[0] ~ B[j]가 모두 배치가 끝난 상황으로 이해하면 된다.- 이 경우
CACHE[k][i][j]의 값은CACHE[k-1][i-1][j] + A[i]*0과 같을 것이다.
Case 3) k번째 열에 0, B[j]가 오는 경우
| K | ... | k-1 | k |
|---|---|---|---|
| A | ... | ... | 0 |
| B | ... | ... | B[j] |
0 ~ k-1열에A[0] ~ A[i],B[0] ~ B[j-1]가 모두 배치가 끝난 상황으로 이해하면 된다.- 이 경우
CACHE[k][i][j]의 값은CACHE[k-1][i][j-1] + 0*B[j]과 같을 것이다.
Case 4) k번째 열에 A[i], B[j]이 오는 경우
| K | ... | k-1 | k |
|---|---|---|---|
| A | ... | ... | A[i] |
| B | ... | ... | B[j] |
0 ~ k-1열에A[0] ~ A[i-1],B[0] ~ B[j-1]가 모두 배치가 끝난 상황으로 이해하면 된다.- 이 경우
CACHE[k][i][j]의 값은CACHE[k-1][i-1][j-1] + A[i]*B[j]과 같을 것이다.
결론적으로 CACHE[k][i][j]의 값은 상술한 4가지 경우의 수중 가장 큰 녀석으로 결정해주면 된다.
다만, 나는 아래의 주의점을 빠르게 캐치하지 못해서 꽤나 고전했다.
i또는j가 0일 때는 Case 2, 3, 4의 점화식을 계산할 때 매우 주의해주어야 한다.- 처음에는
A또는B의 어떤 수도 사용하지 않은 상황이라고만 생각하고 아래와 같이 작성했었다.
// Case 2
if (i != 0)
{
CACHE[k][i][k] = max(CACHE[k][i][j], CACHE[k-1][i-1][j]);
}
else
{
CACHE[k][i][j] = max(CACHE[k][i][j], 0);
}- 그런데 잘 생각해보면 위의 코드는 그 표현이 많이 단순화되었을 뿐이지, 사실
CACHE[k-1][i-1][j]인 경우를 고려하고 있는 것이다. - 따라서, 무작정
else에서 0과 대소를 비교할 것이 아니라, 해당 경우가 가능할 때만 대소를 비교해주어야 한다.
// Case 2
if (i != 0)
{
CACHE[k][i][k] = max(CACHE[k][i][j], CACHE[k-1][i-1][j]);
}
else if (k - 1 >= j) ///< NOTE! Possible Case Only!
{
CACHE[k][i][j] = max(CACHE[k][i][j], 0);
}#include <iostream>
#include <vector>
#include <iostream>
using namespace std;
const size_t kMaxN = 400 + 1;
const int kMinValue = -1 * (401 * 100 + 1);
size_t N;
vector<int> A;
vector<int> B;
int CACHE[kMaxN][kMaxN][kMaxN];
int Solve(void)
{
if (A.size() == 0 || B.size() == 0)
{
return 0;
}
// Initialize
for (size_t k = 0; k < kMaxN; ++k)
{
for (size_t i = 0; i < kMaxN; ++i)
{
for (size_t j = 0; j < kMaxN; ++j)
{
CACHE[k][i][j] = kMinValue;
}
}
}
for (size_t k = 0; k < kMaxN; ++k)
{
CACHE[k][0][0] = max(0, A[0] * B[0]);
}
CACHE[0][0][0] = A[0] * B[0];
// Iteration
for (size_t k = 1; k < N; ++k)
{
for (size_t i = 0; i < min(k + 1, A.size()); ++i)
{
for (size_t j = 0; j < min(k + 1, B.size()); ++j)
{
if (k > i && k > j)
{
CACHE[k][i][j] = max(CACHE[k][i][j], CACHE[k - 1][i][j]);
}
if (i != 0)
{
CACHE[k][i][j] = max(CACHE[k][i][j], CACHE[k - 1][i - 1][j]);
}
else if (k - 1 >= j)
{
CACHE[k][i][j] = max(CACHE[k][i][j], 0);
}
if (j != 0)
{
CACHE[k][i][j] = max(CACHE[k][i][j], CACHE[k - 1][i][j - 1]);
}
else if (k - 1 >= i)
{
CACHE[k][i][j] = max(CACHE[k][i][j], 0);
}
if (i != 0 && j != 0)
{
CACHE[k][i][j] = max(CACHE[k][i][j], CACHE[k - 1][i - 1][j - 1] + A[i] * B[j]);
}
else
{
CACHE[k][i][j] = max(CACHE[k][i][j], A[i] * B[j]);
}
}
}
}
return CACHE[N - 1][A.size() - 1][B.size() - 1];
}
int main(void)
{
// For Faster IO
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// Read Input
cin >> N;
for (size_t it = 0; it < N; ++it)
{
int card;
cin >> card;
if (card != 0)
{
A.emplace_back(card);
}
}
for (size_t it = 0; it < N; ++it)
{
int card;
cin >> card;
if (card != 0)
{
B.emplace_back(card);
}
}
// Solve
cout << Solve() << '\n';
return 0;
}
Pseudo-worker