백준 15678번 - 연세워터파크

* 문제 링크

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

15678번: 연세워터파크

 

 

 

 

문제 내용 요약

 

매년 여름 연세대 (특히 도서관, 서문) 에서는 깜짝 워터파크가 개장하는데,

 

잘 즐기라고 징검다리를 놓아두고 게임을 만들었는데, 부적절한 점수작을 하는 놈들이 있어서 다음과 같은 규칙을 정했다.

 

 

징검다리 N (2 ≤ N ≤ 100,000) 개가 있고, 각각 1 ~ N의 번호가 붙어있다. 이 중에 하나는 시작점으로 올라타야한다.

 

징검다리를 건널 때는 징검다리 번호의 차가 D (1 ≤ D ≤ N-1) 이하여야 한다.

 

징검다리는 정수 K_i (-10^9 ≤ K_i ≤ 10^9)가 쓰여있고, 

 

어떤 징검다리도 2번 이상 밟지 않고 원하는대로 밟은 뒤, 나오고 싶을 때 나온다.

 

그렇게 시작점 포함해서 밟은 징검다리에 쓰인 정수의 합이 최대가 되어야 한다.

 

 

 

 

힌트 - 5977번과의 차이점

 

백준 단계별로 풀어보기에는 5977번 - Mowing the Lawn 다음 문제로 나와있으며,

 

세그먼트 트리, 덱, 또는 우선 순위 큐를 써서 최적화하라고 나와있다.

 

5977번에서 배운대로 이번에도 덱을 써서 최적화를 해보았다.

 

 

 

https://syerco0.tistory.com/5

백준 5977번 - Mowing the Lawn

 

 

저번 글로 썼던 문제의 해결 방법을 보고 오면 쉽게 이해하고 풀 수 있다. 중복되는 설명은 적지 않을 것이다.

 

 

5977번의 문제에서는 모든 소는 0 이상의 효율을 가지고 있지만,

 

연세워터파크는 음수의 값을 가진 징검다리가 있다.

 

또한 원하는 시작점에 올라타고 원하는대로 바로 내려올 수도 있다.

 

 

점화식이 약간 다르겠지만, 큰 틀은 바뀌지 않아 점화식을 구하는 데에 어려움은 적을 것이다.

 

 

 

 

접근법

 

문제 자체에서는 D 이하의 차이의 징검다리 내에서 왔다리갔다리가 가능하지만,

 

그냥 1부터 N으로 가는 방향으로만 이동하는 것과 차이가 없다는 것은 이해할 것이라 생각한다.

 

i 번째는 무조건 밟고 그 전에 밟는 거를 j번째라고 하자.

 

점화식을 구해보자. i 번째 징검다리를 밟는다고 하고, 그 전에 밟는 거를 j 번째 징검다리라고 하면,

 

m[i] 의 후보는 m[j] + k[i] (i-D ≤ j ≤ i-1) 이며, 이 중에 최댓값이 m[i] 가 될 것이다. 맞나?

 

하나 빠졌다. 바로 시작점을 i번째 징검다리로 정하는 경우다.

 

 

 

이전의 징검다리들이 모두 음수의 정수를 가지고 있다고 생각해보자.

 

그것들을 밟고 밟으면 결국 소계는 (음수) + k[i] , i번째를 시작점으로 하는 0 + k[i] 보다는 작다.

 

그래서 k[i] 하고도 비교를 해줘야 한다.

 

 

 

그렇게 해서 m[i]를 구해준 것은 덱에 넣어서 최댓값 뽑아내는 데에 쓰면 된다.

 

5977번 문제와 다르게 최댓값을 뽑아주는 덱으로 최적화해주자.

 

 

 

 

여담으로 k[i] 는 고정이라 최적화를 약간 더 할 수 있긴 하겠지만

 

정말 소소하고 굳이 더 고치기 귀찮아서 패스했다.

 

 

 

 

내 코드

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