백준 5977번 - Mowing the Lawn

* 문제 링크

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

5977번: Mowing the Lawn

 

 

문제 내용 요약

 

엄청 예쁜 잔디밭 대회에서 농부 John씨가 우승하고 싶은데, 작년 대회 이후 흥청망청 놀다가 게을러져버렸다.

 

그래서 N (1 <= N <= 100,000) 마리의 소들한테 일을 시키려는데,

 

i번째 소는 E_i (0 <= E_i <= 1,000,000,000) 만큼의 일을 할 수 있다.

 

근처 소들 K (1 <= K <= N) 마리 이상 모이면 얘네들도 흥청망청한단다.

 

그래서 K 초과의 연속된 소 없이 최대한의 뽕을 뽑을 수 있는 소들을 선택했을 때의

 

효율의 값을 구하자.

 

 

 

접근법

 

다이나믹 프로그래밍을 사용하여 부분을 구할 적에 마지막 뭉텅이에 있을 소들의 수를 기준으로 해보자.

 

j = i 라면 i 번째 소가 포함되지 않는다는 것을 의미한다.

 

i번째 값( = m[i] )을 구할 때, 마지막 뭉텅이가 j번째 (0 <= i - j <= K ) 이후의 소까지를 포함한다고 하자.

 

그렇다면 j번째 소는 제외, s[i] - s[j] + m[j-1] 가 m[i]의 후보가 된다. ( Let ∑ E_x (x = 1 to i) = s[i] )

 

가능한 j에 대한 모든 후보값 중에 최대가 m[i]가 될 것이니, 이걸 N번째까지 하면 되시겠다.

 

 

하지만 이대로 값을 구하려하면, 시간복잡도는 O(N^2)이므로,

 

여기에서 최대 N이 100,000이기 때문에 최적화가 필요함을 느끼게 된다.

 

이 문제는 "단계별로 풀어보기"에 포함된 문제로서, 작은 설명란에 다음 문제를 바탕으로 최적화하라고 되어있다.

 

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

11003번: 최솟값 찾기

 

간단히 설명하자면, 덱을 이용한 최솟값 찾기로 이 DP를 최적화하라는 것이다.

 

s[i] - s[j] + m[j-1] 에서 s[i]는 고정, s[j] - m[j-1] 의 최솟값일 때, m[i] 가 최대가 될 것이기 때문에,

 

덱에 s[j] - m[j-1] 와 위치값 j를 덱에 저장하고 최솟값을 꺼내며 m[i] 를 구해주자.

 

만약 덱을 이용해 최솟값을 구하는 방법을 모르겠다면, 바로 위 문제부터 풀어보자.

 

안타깝게도 저 문제를 풀 적에는 블로그를 안 만들어서 내 설명글은 없다. 다른 곳을 참고하자.

나중에 안 까먹고 안 귀찮으면 설명글을 써야겠다. (안 할 가능성 높다는 뜻)

 

최종적으로 O(N)으로 구할 수 있으니 매우 안정적으로 답이 구해진다.

 

 

 

내 코드

#include <iostream>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
ll s[100010];
ll m[100010];
int main() {
	int n,k;
	ll t;
	cin>>n>>k;
	deque<P> q;
	q.push_front(P(0,0));
	for(int i=1;i<=n;i++) {
		scanf("%d",&t);
		s[i]=s[i-1]+t;
		while(q.front().second<i-k) q.pop_front();
		while(!q.empty()&&q.back().first>=s[i]-m[i-1]) q.pop_back();
		q.push_back(P(s[i]-m[i-1],i));
		m[i]=s[i]-q.front().first;
	}
	cout<<m[n];
}