백준 2031, 이 쿠키 달지 않아!

개요

문제 링크
골드 2, DP, Bisect
길이가 D인 구간을 K개 사용해 최대한 많은 점을 덮기

---

접근

1. K가 10인게 함정인 문제. "덮는다" 에 대한 생각이 쉽지 않아서 까다로운 문제였다. 우선 어떻게 덮는게 최선인지 생각해야 하는데, 덮는 구간의 시작과 끝은 항상 N개의 점 중 하나를 포함하는 것이 이득이다. 굳이 빈 구간에 양끝점을 둘 필요가 없다.
2. 그럼 전체 점을 정렬하고, 각 점 a[i]에 대해 a[i]-D의 위치를 lower bound로 구해두자. 그 위치를 p라고 하면, 길이가 D인 구간에 대해 i-p개의 점이 존재하는 것이다.
3. 나머지는 knapsack이랑 비슷하게 생각하면 된다. j개의 구간을 이용해 i까지 덮는 경우를 저장한 2차원 dp[i][j]를 이용하고, 업데이트는 다음과 같이 한다.

    dp[i][j]=max{
        // 1. i를 덮지 않고 j개의 구간을 사용한 경우
        dp[j][i-1],
        // 2. i를 덮는 구간을 i에만 사용한 경우
        dp[j-1][i-1]+1,
        // 3. i를 덮는 구간을 a[i]-D부터 a[i]까지 사용한경우
        dp[j-1][p[i]]+(i-p[i])
    }

   이해가 단번에 안될수도 있는데, p[i]의 개념을 잘 잡는게 문제의 핵심인 것 같으니 천천히 이해해보자.

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define N 1000001
#define K 11
#define low lower_bound
int dp[K][N],a[N],p[N];
int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int t,n,d,k;
    cin>>t>>n>>d>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a,a+n+1);
    k=min(k,n);
    for (int i=1;i<=n;i++) {
        p[i]=low(a,a+n+1,a[i]-d+1)-a-1;
        p[i]=max(p[i],0);
    }
    for (int j=1;j<=k;j++)
        for (int i=1;i<=n;i++) {
            int &r=dp[j][i];
            r=max(dp[j][i-1],dp[j-1][i-1]+1);
            r=max(r,dp[j-1][p[i]]+(i-p[i]));
        }
    cout<<dp[k][n];
}