[P5] 백준 15678번 연세워터파크 C++ 덱, 덱을 이용한 다이나믹 프로그래밍

리뷰

 

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

처음엔 우선순위 큐를 활용한 로직을 구현하였으나, 제출할 때 마다 엣지케이스가 존재해 Fail을 받았다.

이후 덱을 사용한 최적화를 진행하여 AC를 받게 되었다.이 과정에서 int타입으로는 받을 수 없는 결과가 존재함을 알게 되었다.

우선순위 큐를 활용해 그리디하게 접근해도 괜찮을 듯 싶다만 덱이 가장 최적화된 답을 도출할 것 같다.

 

 

전역 변수

• n : 징검다리의 개수를 저장할 변수
• d : 건널 수 있는 범위를 저장할 변수
• lst : 징검다리에 표시된 값을 저장할 정수형 배열

 

함수

없음

 

 

문제풀이

1. n, d에 값을 입력 받고, n개의 징검다리 정보를 lst배열에 입력 받아 준다.
2. pair<int, long long>타입의 덱 deq를 초기화 한다.
3. 징검다리를 순회하며 덱이 비지 않았다면 덱의 맨 앞 요소보다 작은 인덱스는 모두 pop해준다.
4. 현재 징검다리에 덱의 맨 앞의 요소를 더한값과 현재 징검다리의 값 중 더 큰 값을 현재 징검다리에 저장해 준다.
5. 다시 덱의 뒤부터 순회하며 현재 징검다리의 값 보다 작은 값들을 모두 빼내어 준다.
6. 덱에 현재 징검다리의 인덱스와 값을 뒤에서 추가해 준다.
7. 탐색을 마친 후에 lst배열에 저장된 값 중 가장 큰 값을 출력해 준다.

 

트러블 슈팅

1. 처음엔 우선순위 큐를 통해 그리디하게 접근해 주었었다.
2. cur이라는 변수를 통해 현재까지의 값을 저장해 주고, ans에 cur의 최대값을 갱신하는 식이었다.
3. 앞에서 부터 탐색하며 현재 징검다리의 값이 양수라면 우선순위 큐를 clear해준 후 cur에 더해주거나, 현재 징검다리의 값이 cur보다 크면 갱신해 주었다.
4. 만약 위 조건에 해당하지 않는다면 우선순위 큐에 인덱스와 값을 저장하고 큐의 크기가 d보다 커졌을 경우 최적의 요소를 뽑아내고 그보다 인덱스가 작은 것들은 모두 제거해 주었다.
5. ans를 long long타입으로 설정하지 않아서인지 엣지케이스가 존재해서인지 모르겠지만 1%에서 Fail을 받았다.
6. 이후 덱을 사용해 구현하니 우선순위 큐 보다 더 최적화 된 방법으로 문제에 접근할 수 있었다.

 

참고 사항

• 왼쪽의 징검다리 부터 시작하여 오른쪽으로 이동하는 로직을 구현하여도 최적화된 풀이를 구현할 수 있다.
• lst배열 자체를 메모제이션 형식으로 진행하는 방식으로 접근하면 된다.

 

정답 코드

#include<iostream>
#include<deque>
#include<algorithm>
#define ll long long
using namespace std;

int n, d;
ll lst[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> d;
	for (int i = 0; i < n; ++i) cin >> lst[i];

	deque<pair<int, ll>> deq;
	for (int i = 0; i < n; ++i) {
		while (!deq.empty()) {
			if (deq.front().first < i - d) deq.pop_front();
			else {
				lst[i] = max(lst[i], lst[i] + deq.front().second);
				break;
			}
		}
		while (!deq.empty()) {
			if (deq.back().second < lst[i]) deq.pop_back();
			else break;
		}
		deq.push_back({ i, lst[i] });
	}
	cout << *max_element(lst, lst + n);
}