[BOJ 15678 // C++] 연세워터파크

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15678번 문제인 연세워터파크이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15678

15678번: 연세워터파크

이 문제에서는 DP를 이용하여 주어진 놀이에서 얻을 수 있는 최대 점수를 구하면 된다.

 

먼저, 문제에 주어진 놀이에서는 징검다리를 뛰어다닐 수 있는 방향이 정해져 있지 않지만, 양방향으로 뛰어다니면서 밟아 얻는 징검다리 칸은 밟은 징검다리를 한쪽 끝에서부터 반대쪽 끝까지 순서대로 밟을 수 있으므로 1번 징검다리에서 N번 징검다리 방향으로 순서대로 징검다리를 밟아나가는 경우만 고려해도 상관없다.

 

먼저, DP를 만들기 위해 다음과 같은 관계를 관찰해보자.

 

(1~(i+1)번째 징검다리를 밟아 얻을 수 있는 최대 점수)가 될 수 있는 후보는

 

1) 1~i번째 징검다리를 밟아 얻을 수 있는 최대 점수

2) i+1번째 징검다리에서 D 이하로 떨어져있는 각 왼쪽 징검다리를 밟아 얻을 수있는 최대 점수와 i+1번째 징검다리의 점수의 합

3) 그냥 i+1번째 징검다리만 밟는 경우

 

의 세 가지이다. 이것을 구현하기 위해, 1은 최종으로 출력할 ans 변수를 만들어 관리하고 배열을 만들어 각 징검다리가 밟히고 그 칸에서 더 오른쪽 징검다리를 밟지 않는 경우의 수들을 저장해둔 다음 최댓값을 계속 읽어오는 DP 코드를 작성할 수 있다.

 

그러나, 위의 알고리즘을 그대로 구현하면 이전에 최댓값을 얻어온 과거의 값보다 왼쪽 징검다리를 밟고 오른쪽 징검다리를 밟지 않는 경우는 더 이상 살펴볼 필요가 없음에도 이 경우를 계속 살피게 된다.

이는 불필요한 동작이며, 이를 개선하기 위해 우선순위 큐(priority queue)를 이용해볼 수 있다.

이전 징검다리에 적혀있는 값을 우선순위 큐에 넣어서 보관한다면, 우선순위 큐에서 이전 징검다리에 적혀있는 최댓값을 손쉽게 얻을 수 있기 때문이다. 

뛸 수 있는 범위의 징검다리인지를 확인하기 위해 우선순위 큐에 점수와 함께 징검다리 번호를 pair를 이용하여 같이 넣는다면 이 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
using std::cin;
using std::cout;
using std::pair;
using std::priority_queue;
using std::max;

priority_queue<pair<long long, int>> pq;
long long ans;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, D;
    cin >> N >> D;
    long long current; pair<long long, int> temp;
    cin >> current;
    ans = current; pq.push({current,0});
    for (long long i = 1;i < N;i++) {
        cin >> current;
        while (1) {
            if (i - pq.top().second > D) pq.pop();
            else break;
        }
        temp = pq.top(); pq.pop();
        pq.push({ max(temp.first + current, current),i });
        if (ans < pq.top().first) ans = pq.top().first;
        
        pq.push(temp);
    }
    cout << ans;

    return 0;
}