열쇠고리 (JUNGOL 4822)

https://jungol.co.kr/problem/4822?cursor=MTEsMCw2

---

아이디어

몇개의 열쇠고리를 골랐을 때 그 열쇠고리들을 다 설치할 수 있을 필요충분조건은 모든 열쇠고리에 대해서 a-1값의 합이 -1이상이라는 것입니다. 그러므로 dp[i]를 지금까지의 a-1의 합이 i일때의 최대 만족도라고 정의하면 문제를 해결할 수 있습니다.

 

이때 dp가 음수가 될 수 있으므로 인덱스에 N씩 더해서 저장해주고, N초과의 값은 그냥 N으로 처리해도 되므로 dp[0]부터 dp[2N]까지만 사용해주면 됩니다.

---

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll dp[4040]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b,j;

    cin>>N;

    for (i=0;i<=2*N;i++) dp[i]=-1e18;
    dp[N]=0; //인덱스에 N씩 더하기

    for (i=1;i<=N;i++)
    {
        cin>>a>>b;

        if (a==0)
        {
            for (j=0;j<2*N;j++)
                dp[j]=max(dp[j],dp[j+1]+b);
        }
        else
        {
            for (j=2*N;j>=0;j--)
                dp[min(j+(a-1),2*N)]=max(dp[j]+b,dp[min(j+(a-1),2*N)]);
        }
    }

    ll res=0;
    for (i=N-1;i<=2*N;i++)
        res=max(res,dp[i]);

    cout<<res;
}