BOJ 3998 - 단백질 식별

문제 태그 : https://www.acmicpc.net/problem/3998

문제 소개

N개의 질량조건이 주어진다. 이 중 가장 큰 값과 단백질의 전체 질량이 똑같은 단백질 구조 중 주어진 질량조건에 단백질의 prefix 질량과 suffix 질량이 가장 많이 포함되어있는 단백질 구조를 출력하시오.

예제) 353.16992는 가장 큰 값으로 단백질이 P하나와 Q두개로 이루어져 있다는 것을 알려준다. 이때 구조를 PQQ또는 QQP로 배치하게 되면 P=97.05276 Q=128.05858 PQ=225.11134 PQQ=353.16992 4개로 가장 많은 질량조건을 만족시킬 수 있다.

문제 풀이

일단 몇 가지 관찰을 하는 것이 중요하다. 정말 단순하고 간단한 것 일수 있지만, 하나하나가 정말 강력하게 작용하는 관찰들이다.

1. 질량 조건중 가능성이 있는 것과 없는 것이 정해져 있다. 1.00000 과 같은 경우는 아예 고려할 필요가 없다.
2. 같은 질량을 서로 다른 경우로 만들 수 없다. P와 Q의 숫자를 주목해서 고려하거나, 아니면 직접 돌려서 뽑아보면 400개 이하의 경우일 때는 서로 다른 갯수를 더해 같은 숫자를 만드는 것이 절대 불가능하다는 것을 알 수 있다. 
1과 2를 합쳐서 말하자면 어떠한 질량조건을 만족하는 P와 Q의 집합은 제한내에서 유일하거나 존재하지 않는다.
2.1 따라서 전체 P와 Q의 갯수는 유일하게 정해진다.
3. prefix가 정해지면 suffix가 정해진다. 전체의 갯수가 유일하게 정해졌으므로, 전체 - prefix가 suffix가 된다.

일단 suffix를 무시하고 prefix만 존재한다고 생각해보자. 우리는 문제의 조건에서 구해놓은 n개의 p와 m개의 q를 활용해 최대한 많은 조건을 포함해야 한다... 여기서 쉬운 DP문제가 하나 떠오르게 된다.
(r,c)에서는 (r+1,c)또는 (r,c+1)로 이동을 한다. 각 칸에는 점수가 쓰여있다. (1,1)에서 (n,m) 까지 이동을 하면서 가장 많은 점수를 휙득할 수 있는 방법을 출력하시오.

위의 문제와 정확히 같은 문제이다. 질량 조건들을 맞는 위치에다가 칸의 가중치로 변환시키고 최대한 많은 점수를 휙득하게 하면 된다. 하지만 suffix도 같이 고려 해야한다는 문제가 생긴다. 
이를 해결하기 위해 점수를 먹을때 정반대의 점수도 같이 먹는다고 생각하자. 예를 들어 3*5의 필드가 있을때 0,2에 가게 된다면 2,2의 점수를 같이 먹는다는 것이다. 
하지만, 반대칸에서 한 번 방문에서 한 번 먹게 되어 중복이 될 수 있다는 것이다. 글의 설명이 이상하므로 그림을 함께 준비했다. 

왼쪽의 그림처럼 (0,2)에 왔다는 것은 prefix가 2개의 Q를 사용했다는 것을 의미한다. 이는 suffix가 2개의 P와 2개의 Q로 이루어졌다는 것을 의미하고 빨간 점의 위치는 자동적으로 먹어진다. 하지만 나중에 이동할 때 저 위치로 이동하면 double counting이 되므로 DP를 쓸 수 없다.

생각을 바꿔서 1~n+m까지 prefix를 구하는 것이 아니라 앞의 절반의 prefix 뒤의 절반의 suffix를 제한한다고 생각해보자. 이동범위가 절반까지이기 때문에 위의 경우처럼 double counting 되는 것은 없을 것이다. 따라서 문제는 두 개를 한번에 움직이는 것으로 바뀌었다.

DP[i][j][k]는 둘의 위치의 x+y가 i이며, 하나의 x값은 j, 나머지 하나의 x값은 k일때의 얻은 점수의 최댓값으로 설정하자. 두 개의 이동 방법은 4가지 이기 때문에, 둘의 위치가 겹쳐도 쉽게 DP식을 전개해줄 수 있다. 

DP값을 구하면서 역추적을 미리 해놓는 것으로 문제를 $O(M^3)$에 해결할 수 있다. (M은 길이)

홀 짝에 의한 예외처리가 정말 해줄 것이 많고, 까다롭다. 

코드

※ 오래 고민해 보지 않고 문제 수, 경험치만을 위해서 코드를 복붙하는 등의 행위는 큰 페널티를 받을 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pdi;
typedef pair<char,char> pcc;
#define ff first 
#define ss second
int dp[404][404][404];
int cnt[404][404];
pdi arr[1010101];
pcc rev[404][404][404];
int main(){
    ll i,j,k,l,m,n,ccnt=0;
    for(i=0;i<=400;i++){
        for(j=0;j<=400;j++){
            ccnt++;
            arr[ccnt]={9705276*i+12805858*j,i*500+j};
        }
    }
    sort(arr+1,arr+1+ccnt);
    scanf("%lld",&n);
    ll mval=0.0;
    ll mi=0;
    ll mj=0;
    while(n--){
        long double p;
        cin>>p;
        ll x=round(100000*p);
        ll idx1=lower_bound(arr+1,arr+1+ccnt,make_pair(x,(ll)-5))-arr;;
        if(arr[idx1].ff==x){
            if(mval<x){
                mval=x;
                mi=arr[idx1].ss/500;
                mj=arr[idx1].ss%500;
            }
            cnt[arr[idx1].ss/500][arr[idx1].ss%500]++;
        }
    }
    n=mi+mj;
    ll hap=(n-1)/2;
    for(i=0;i<=hap;i++){
        for(j=0;j<=hap-i;j++){
            cnt[i][j]+=cnt[mi-i][mj-j];
            cnt[mi-i][mj-j]=0;
        }
    }
    hap=n/2;
    dp[0][0][0]=cnt[0][0];
    for(i=1;i<=hap;i++)
        for(j=0;j<=i;j++)
            for(k=0;k<=i;k++){
                if(j!=0&&k!=0&&dp[i-1][j-1][k-1]>dp[i][j][k]){
                    dp[i][j][k]=dp[i-1][j-1][k-1];
                    rev[i][j][k]=make_pair('P','P');
                }
                if(j!=i&&k!=0&&dp[i-1][j][k-1]>dp[i][j][k]){
                    dp[i][j][k]=dp[i-1][j][k-1];
                    rev[i][j][k]=make_pair('Q','P');
                }
                if(j!=0&&k!=i&&dp[i-1][j-1][k]>dp[i][j][k]){
                    dp[i][j][k]=dp[i-1][j-1][k];
                    rev[i][j][k]=make_pair('P','Q');
                }
                if(j!=i&&k!=i&&dp[i-1][j][k]>dp[i][j][k]){
                    dp[i][j][k]=dp[i-1][j][k];
                    rev[i][j][k]=make_pair('Q','Q');
                }
                if(j!=k) dp[i][j][k]+=(cnt[j][i-j]+cnt[k][i-k]);
                else dp[i][j][k]+=cnt[j][i-j];
                if(j>mi||k>mi||i-j>mj||i-k>mj) dp[i][j][k]=-17;
            }
    int ans=0;
    int ansj,ansk;
    for(j=0;j<=hap;j++)
        for(k=0;k<=hap;k++)
            if(dp[hap][j][k]>ans&&j+k<=mi&&hap*2-j-k<=mj){
                ans=dp[hap][j][k];
                ansj=j;
                ansk=k;
            }
 
    string s1,s2;
    ll cntq=0;
    ll fl=hap;
    while(fl){
        s1+=rev[fl][ansj][ansk].ff;
        s2+=rev[fl][ansj][ansk].ss;
        if(rev[fl][ansj][ansk].ff=='P') ansj--;
        else cntq++;
        if(rev[fl][ansj][ansk].ss=='P') ansk--;
        else cntq++;
        fl--;
    }
    reverse(s1.begin(), s1.end());
    if(n%2&&mj!=cntq) cout<<s1<<'Q'<<s2;
    else if(n%2) cout<<s1<<'P'<<s2;
    else cout<<s1<<s2;
}