백준 2031번 - 이 쿠키 달지 않아!

www.acmicpc.net/problem/2031

2031번: 이 쿠키 달지 않아!

 

재미있는 DP문제였습니다.

다이어트 효과가 최대가 되려면 다이어트가 효과가 유지되는 시간안에 음식이 가장 많이 포함되어 있어야 합니다.

우선 단순하게 K=1일때의 문제를 생각해 봅시다.

위에서 정의한 문제를 'D만큼의 범위안에 포함할 수 있는 원소의 최대 개수'로 치환할 수 있습니다.

그렇다면 이 문제는 정렬과 이분탐색을 이용하면 O(NlogN)에 풀릴 수 있을것 같습니다.

n번째 음식을 시작으로 D분동안 얼마나 많은 음식을 먹을 수 있는지 계산하면 됩니다.

 

예제 입력1

20 7 5 2

9 15 7 12 14 9 3

문제에서 위의 예제 입력으로 예를들면, 정렬시 [3, 7, 9, 9, 12, 14, 15] 이고

D=5이므로 [2, 3, 3, 2, 3, 2, 1] 이라는 결과를 얻을 수 있습니다.

K=1일때 최댓값인 3이 정답이 되겠지만 K의 범위는 (1 ≤ K ≤ 10)이므로 D분을 K만큼 적절하게 분배해야 합니다.

이때 완전탐색시 N의 범위는 (1 ≤ N ≤ 1e6) 이므로 시간초과를 피하지 못합니다.

 

이 문제는 DP를 이용하여 해결 할 수 있습니다.

i번째 음식까지 효과를 j번 사용했을때, 포함할 수 있는 음식의 최댓값을 dp[i][j]라고 한다면  (1 ≤ N*K ≤1e7) 이므로

공간복잡도와 시간복잡도를 모두 만족할 수 있습니다.

 

아래 코드에서는 전처리로 설명했던 'n번째 음식을 시작으로 D분안에 포함되는 음식의 개수'를

'n번째 음식에서 D분이 끝날때 포함되는 음식의 개수'로 바꾸어 전처리하고 DP를 수행했습니다.

 

• C++ 전체 코드

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

int T,N,D,K;
int m[1000002]{};
int mm[1000002]{};
int dp[1000002][11]{};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>T>>N>>D>>K;
    for(int i=1; i<=N; i++) cin>>m[i];
    sort(m, m+N+1);

	// mm[i] : i번째 음식에서 D만큼의 효과가 끝났을때 포함되는 음식의 개수
    for(int i=1; i<=N; i++) {
        mm[i] = i - (lower_bound(m+1, m+N+1, m[i]-D+1)-m) + 1;
    }
	
    for(int j=1; j<=K; j++) {
        for(int i=1; i<=N; i++) {
            int t = mm[i];
            dp[i][j] = max({dp[i-1][j], t + dp[i-t][j-1]});
        }
    }

    cout<<dp[N][K];
}