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

 

문제

(연세대학교 도서관, 2016년 7월)

연세대학교에서는 매년 여름 깜짝 워터파크를 개장한다. 이 워터파크가 발생할 장소는 알 수 없지만, 보통 도서관이나 서문 쪽에 주로 개장한다는 사실만이 알려져 있다.

워터파크 개장을 막는 것이 힘들다고 판단한 학교에서는 차라리 학생들이 워터파크를 더 즐길 수 있도록 정수 Ki (-109 ≤ Ki ≤ 109)가 쓰여진 징검다리 N개를 놓아 두었다. 수업이 끝나고 친구들과 집에 가던 준호는 문득 이 징검다리를 이용해 여러 명이 즐길 수 있는 재미있는 게임을 하나 생각해냈다.

• 각 사람은 시작점으로 쓸 징검다리 하나를 아무 것이나 하나 고른다.
• 시작점에서 출발한 뒤 계속 점프하여 징검다리를 몇 개든 마음대로 밟은 뒤, 나오고 싶을 때 나온다. 시작점에서 바로 나오는 것도 가능하다.
• 시작점을 포함해, 밟은 모든 징검다리에 쓰여진 정수의 합이 가장 큰 사람이 이긴다.

이 규칙에 따라 게임을 하던 준호는, 제자리 점프를 이용해 10억점을 만드는 친구를 본 뒤 규칙을 좀 더 추가하기로 하였다. 추가된 규칙은 아래와 같다.

• N개의 모든 징검다리에 순서대로 1 ~ N의 번호를 붙인다. U번 징검다리에서 V번 징검다리로 점프하기 위해서는, U와 V의 차이가 미리 정해진 값 D 이하여야 한다.
• 어떤 징검다리도 두 번 이상(한 번을 넘게) 밟을 수는 없다.

이제 다시 게임을 진행하려 한다. 이 게임에서 준호는 최대 몇 점을 얻을 수 있을까?

입력

첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1)

이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-10^9 ≤ Ki ≤ 10^9)

출력

가능한 최대 점수를 출력한다.

예제 입력 1 

10 2
2 7 -5 -4 10 -5 -5 -5 30 -10

예제 출력 1 

40

예제 입력 2 

3 2
-4 -2 -7

예제 출력 2 

-2

 

문제 풀이

[자료구조] 모노토닉 큐 (Monotonic Queue)

 

[BOJ / C++] 11003 : 최솟값 찾기

 

11003번 문제를 풀며 '모노토닉 큐'라는 자료구조에 흥미가 생겨 하나 더 풀어보려고 찾은 문제다.

이번에 차이점이 있다면... 모노토닉 큐에 다이나믹 프로그래밍일 곁들인....

 

이번 문제를 풀 때에는 11003번 문제와는 다르게 인덱스만 저장하지 않고, 정석적으로 해시로 저장을 했다.

또 다른 점이라고는, 최적해를 구해야 하는 문제이기 때문에 이를 판별하여 덱에 선택적으로 넣는 방식을 취했다.

 

문제 풀이 순서를 정리해보면 아래와 같다.

1. 원본 배열의 각 원소 입력
2. 덱이 비어있지 않다면
   1. 인덱스가 탐색 범위 D에 맞지 않는 원소가 덱에 들어있다면 지난 구간의 최대값이므로 덱의 front에서 제거한다.
   2. 덱이 비어있지 않다면 (최대값이 들어있는 front + 현재 입력된 원본 배열의 원소) 와 현재 입력된 원본 배열의 원소 중 더 큰 값을 취해 덱의 back에 push한다.
      1. 이때, 덱의 맨 뒤에 있는 값보다 지금 덱에 넣으려는 값이 크거나 같다면 back에 있던 값을 제거하고 집어넣는다.

 

 

처음에는 Ki의 범위를 고려하지 못해 result의 최솟값을 0으로 잡았다가 틀렸고,

두 번째에는 Ki의 범위에 따른 deque에 들어갈 수 있는 값의 범위를 int로 잡았다가 틀렸다.

그래서 result의 자료형을 long long으로 변경하고, 최소값을 -1e9 (-10억)으로 잡았고, deque에 들어가는 원소의 값도 long long으로 변경했다. pair의 first는 N의 범위가 int 이내이므로 int로 해도 됐을텐데.... 코드의 자료형이 조금 중구난방인 것이 마음에 걸리긴 하네.

문제 풀이 코드 

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, d;
    deque<pair<long long, long long>> dp; 
    long long result = -1e9; //최소값 -10억

    cin >> n >> d;

    for(int i = 1; i <= n; i++) {
        pair<int, long long> target;
        target.first = i;
        cin >> target.second;

        while(dp.size() && dp.front().first < i - d) {
            // 탐색 범위 d에 맞지 않는 dp 덱의 front 제거
            dp.pop_front();
        }

        if(dp.size()) {
            // dp 덱이 비어있지 않다면 현재 입력된 값 그 자체와 현재 dp 덱 맨 앞의 값 + 현재 입력된 값 중 최대값 구해 넣음
            target.second = max(target.second, dp.front().second + target.second);
        }

        // 결과와 현재 구한 최대값을 비교하여 더 큰 값을 결과에 넣음
        result = max(result, target.second);

        while(dp.size() && dp.back().second <= target.second) {
            // dp 덱의 back에 있는 최대값이 현재 넣으려는 값의 최대값보다 작다면 back 제거
            dp.pop_back();
        }

        dp.push_back(target);
    }

    cout << result << "\n";

    return 0;
}

 

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