숫자 박스
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;
}
Author And Source
이 문제에 관하여(숫자 박스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aram_father/숫자-박스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)