[ BOJ 백준 1983번 - 숫자 박스 ] 해설 및 코드

 

https://www.acmicpc.net/problem/1983

목적

N개의 열, 2개의 행으로 이루어진 숫자 상자들에, 0이 아닌 수들을 순서를 지켜 배치하여, 각 열의 위 아래를 곱해 그 합의 최대값을 만들자.  

 

접근법

1. s[i][j][k]는 1행의 i번째 수나 2행의 j번째 수가 k열에 위치했을 때의 최대값이라고 정한다. 

2. 그러면 s[i][j][k]는 k열에 i번째 수와 j번째 수가 둘 다 위치하거나, 둘 중 하나만 위치하는 경우의 최대값을 취한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
 
const int MN=-40000;
int n,a[2][400],len[2]{},s[400][400][400];
 
int sol(int i, int j, int k){
    if(i==len[0]||j==len[1])return 0;
    int &ref=s[i][j][k];
    if(ref!=MN)return ref;
    ref=MN;
    if(len[0]-i+k<n)ref=max(ref,sol(i, j+1, k+1));
    if(len[1]-j+k<n)ref=max(ref,sol(i+1, j, k+1));
    return ref=max(ref,a[0][i]*a[1][j]+sol(i+1, j+1, k+1));
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    f(i,0,2)f(j,0,n){
        cin>>a[i][len[i]];
        if(a[i][len[i]]!=0)++len[i];
    }
    f(i,0,n)f(j,0,n)f(k,0,n)s[i][j][k]=MN;
    cout<<sol(0, 0, 0);
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.