[KOI] 백준 1983 - 숫자 박스

icpc.me/1983

 

관찰

주어진 숫자 박스에서 숫자를 옮기는 것을 시뮬레이션하면 원하는 답을 구할 수 없을 것이다.

 

각 숫자의 위치는 순서를 바꾸지 않는 범위에서 자유롭게 옮길 수 있다는 점에 주목해보자.

 

그렇다면 숫자들이 모두 한쪽에 치우친 상태이고, 상황에 따라 빈칸을 적절히 남겨두는 방식으로 숫자 박스의 값을 최대화시킬 수 있을 것이다.

 

점화식

이 아이디어를 통해 문제를 해결하고자 한다면 다음과 같은 테이블을 생각할 수 있을 것이다.

 

dp[i][j][k] := i번째 열까지 첫 번째 행에서 빈칸 0을 포함한 j개의 숫자, 두 번째 행에서 빈칸 0을 포함한 k개의 숫자를 사용했을 때 숫자 박스의 최댓값

 

N은 400이하이므로 400 * 400 * 400 * 4(byte) = 256mb가 나와 문제의 메모리 제한인 512mb는 무리 없이 통과할 수 있다.

 

삼중 반복문을 생각했을 때도 시간을 초과하지 않으므로 삼중 반복문 동적 계획법을 사용해서 해결 할 수 있다.

 

점화식의 기본 형태는 다음일 것이다.

 

숫자 박스가 이차원 배열 board[2][n]으로 주어졌을 때

 

dp[i][j][k] = dp[i - 1][j - 1][k - 1] + board[0][j] * board[1][k];

 

하지만 이대로만 사용한다면 숫자를 모두 한쪽으로 밀어 넣은 상태에서 계산한 값을 더하는 것이므로 칸을 적절히 밀어 더 큰 값을 만들 수 있는 상황을 반영해줘야 한다.

 

그 상황은 dp[i][j - 1][k]와 dp[i][j][k - 1]로 표현할 수 있겠다. 물론 이것보다 비우지 않고 계산한 게 더 클 수 있으니 대소 비교를 하여 테이블을 채우면 되겠다.

구현

인덱스에 따른 예외처리에 유의해야 한다. 이를 잘못하면 실제로 계산되어야 할 열이 계산 되지 않을 수 있다.

 

예를 들어 열의 길이가 1이고 위에는 1, 아래에는 -1이 있는 경우 dp[1][1][1]에서 dp[1][0][1]이나 dp[1][1][0]을 고려하게 되면 잘못된 값을 계산하게 된다.

 

각 상황마다 이런일이 일어나는 경우를 처리하도록 하자.

 

전체 코드

#include <iostream>
#include <cstring>
 
using namespace std;
 
int n;
int board[2][401];
int dp[401][401][401];
int up, down;
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int x; cin >> x;
 
            if (!x)
                continue;
 
            if (!i)
                board[i][++up] = x;
            else
                board[i][++down] = x;
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= min(up, i); ++j)
        {
            for (int k = 1; k <= min(down, i); ++k)
            {
                if (j == i && k == i)
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + board[0][j] * board[1][k];
                else if (j == i)
                    dp[i][j][k] = max(dp[i - 1][j - 1][k], dp[i - 1][j - 1][k - 1] + board[0][j] * board[1][k]);
                else if (k == i)
                    dp[i][j][k] = max(dp[i - 1][j][k - 1], dp[i - 1][j - 1][k - 1] + board[0][j] * board[1][k]);
                else
                    dp[i][j][k] = max(dp[i - 1][j - 1][k - 1] + board[0][j] * board[1][k], max(dp[i - 1][j - 1][k], dp[i - 1][j][k - 1]));
            }
        }
    }
 
    cout << dp[n][up][down];
}