[도전 17일차] 숫자 박스 - KOI 고등부 풀이

문제 : 백준 1983 숫자 박스 

문제 링크

 

사용 알고리즘 : DP

 

KOI 2003 고등부 2번

 

풀이:  (잡담이 싫다면 "하하 풀이를 보았다" 부분부터 보면 된다.)

출처 백준

빈칸에 들어있는 수를 0이라 할 때, 모든 열 위아래의 수들을 곱해 더한 합이 최대가 되도록 숫자를 움직이는 것이 목표다. 

단, 각 행에서 숫자들의 순서는 유지되어야 한다. (저 박스를 잡고 적당히 좌우로 기울인다고 생각하면 편하다.)

N이 400 이하로 작으므로 완탐을 돌릴 생각을 할 수도 있지만 불가능한 말씀이다. 매칭 경우의 수의 근사값은 400 C 200 * 400 C 200으로 1억과는 하늘과 땅 차이가 난다. 

 

문제를 곰곰히 생각해보자. 위쪽 행에는 a개의 수, 아래쪽 행에는 b개의 수가 있다고 하자. 

일반성을 잃지 않고 a<=b라고 하면 , b개의 숫자 중에서 a개를 순서에 맞춰 골라 매칭 시키는 것이다. 단, a개에서 최대 n-b개까지 빈공간이랑 매칭 시킬 수 있다.  매우 복잡해진다.

 

다시 생각을 Clear하고 생각해보자. 

N이 적당히 작고, 최대값을 구하는 문제이므로 "이 문제는 DP로 풀릴 가능성이 매우 높다!" 정도는 누구나 눈치 챌 수 있다. 근데 도저히 어떤 점화식을 세워야 될 지 감조차 오지 않는다.

 

하하 풀이를 보았다. 

DP 관계식을 세우는 사고의 과정을 눈여겨보았다.

박스에서 0을 제외하고 한번 생각해보자. 그러면 0이 아닌 수들로 이루어진 수열이 나온다. 이제 위아래로 2개의 수열을 고려해야 하므로 2차원 이상의 DP일 것은 명백하다. 

그러면 이제 고려해야할 요소가 끝났는가? 아니다. 기존 박스의 가로 길이인 N도 고려해주어야 한다. 그러면 3가지 요소를 꼭 고려해야지 문제를 풀 수 있다는 뜻이다. 

 

주목해야할 성질은 다음과 같다. 각 수열의 순서는 항상 유지된다. 각 수열을 A1,A2라 하고 각각의 길이를 N1,N2라 하자. 만약 우리가 1~i 까지 A1을 채운다고 가정하면 이는 반드시 1~i-1까지 채웠을 때 상황에 영향을 받는다는 뜻이다.  A2도 마찬가지다. 이제 헷갈리는 것은 그러면 i번째 칸을 어디다 채울 것인가 하는 것이다. Wow 이제 3번째 요소를 고려할 차례다. 그냥 i번째 항을 K번째 열에 채운다고 하자 . 그러면 아주 놀랍게도 3차원 DP가 완성된다.

칸을 채울 테이블을 DT라 하자.

 

DT[i][j][k] 의 정의

수열 A1에서 1~i 항을 , 수열 A2에서 1~j 항을 박스의 1~k번째 위치까지 채웠을 때 가능한 숫자박스 값의 최대.

DT[i][j][k] 의 관계식

DT[i][j][k] = max (DT[i-1][j][k-1] ,DT[i][j-1][k-1], DT[i-1][j-1][k-1]+ A1_i * A2_j)

1. 위쪽 행의 마지막을 비우고 아래 행의 마지막을 A2_j 로 할 때.
=> DT[i][j-1][k-1] + A2_j * 0
2. 위쪽 행의 마지막을 A1_i로 하고 아래 행의 마지막을 비울 때.
=> DT[i-1][j][k-1] + A1_i * 0
3. 위쪽 행의 마지막을 A1_i, 아래 행의 마지막을 A2_j로 할 때
=> DT[i-1][j-1][k-1] + A1_i * A2_j

 

자 이제 열심히 구현하자!

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define vsort(v) sort(v.begin(),v.end())
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
const int INF = 1e8;
using namespace std;
int n,N1,N2,A1[401],A2[401];
int DT[401][401][401],ans;
void input(){
    fastIO
    cin>>n;
    for(int i=1,k;i<=n;i++){
        cin>>k;
        if(k!=0)
            A1[++N1]=k;
    }
    for(int i=1,k;i<=n;i++){
        cin>>k;
        if(k!=0)
            A2[++N2]=k;
    }
}
int f(int a,int b,int c){
    if(a>c || b>c)
        return -INF;
    if(!a || !b || !c)
        return 0;
    if(DT[a][b][c]!=-INF)
        return DT[a][b][c];
    int k = max(f(a-1,b,c-1),f(a,b-1,c-1));
    return DT[a][b][c] = max (k,f(a-1,b-1,c-1) + A1[a] * A2[b]);
}
void solve(){
    fill(&DT[0][0][0],&DT[N1][N2][n+1],-INF);
    ans = f(N1,N2,n);
}
void output(){
    cout<<ans;
}
int main(){
    input();
    solve();
    output();
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)