[BAE/<JOON> 문제풀이] 2031. 이 쿠키 달지 않아!

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

2031번: 이 쿠키 달지 않아!

 

서론

주어진 각 시간마다 차의 효능이 유지되는 구간을 미리 계산해 시간을 줄이는 문제 

---

풀이

각 음식마다 차의 효능을 얻으면서 먹을 수 있는 구간이 정해져있다.

어떤 음식i 를 먹는 시간이 arr[i]라고 한다면 그 그 음식을 포함해 차의 효능을 얻을 수 있는 구간은 arr[i] - d + 1 분까지 이다. 시간을 정렬하고 lower_bound 함수를 구하면 마지막 음식의 인덱스를 구할 수 있고 그 인덱스를 통해 먹을 음식의 수를 정할 수 있다. 따라서 점화식은 아래와 같다.

• DP[i][j] = i잔의 차를 마셨을 때 j번째 음식까지 먹을 수 있는 음식의 최대 수
• vp[j] = j 번째 음식을 마지막으로 차의 효능이 사라질 경우 먹을 수 있는 음식 중 가장 인덱스가 작은 음식
• cnt =  차의 효능이 유지되는 동안 j 번째 음식을 먹었을 때 먹을 수 있는 음식 수 총합  = j - vp[j] + 1      
• DP[i][j] = max(DP[i - 1][vp[j - 1] + cnt, DP[i - 1][j]

---

코드

 

#include <bits/stdc++.h>
using namespace std;
const long long mod = 10e8 + 7;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int t, n, d, k; cin >> t >> n >> d >> k; vector<int> arr(n + 1), vp(n + 1); vector<vector<int>> dp(k + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];		
	}	
	sort(arr.begin() + 1, arr.end());
	for (int i = 1; i <= n; i++) {
		vp[i] = lower_bound(arr.begin() + 1, arr.end(), arr[i] - d + 1) - arr.begin();
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {		
			int cnt = j - vp[j] + 1;
			int s1 = dp[i - 1][vp[j] - 1] + cnt;
			int s2 = dp[i - 1][j];
			dp[i][j] = (s1 > s2 ? s1 : s2);
			dp[i][j] = dp[i][j] > dp[i][j - 1] ? dp[i][j] : dp[i][j - 1];
		}
	}
	cout << dp[k][n];
	return 0;
}