[백준/C++] 25603번: 짱해커 이동식

문제

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

---

문제 요약

n개의 의뢰 비용이 순서대로 주어진다.

최대한 적게 의뢰를 받으려 한다. 하지만, 연속된 k개 중 하나 이상의 의뢰는 반드시 받아야 한다.

 

위 조건을 만족하면서 의뢰를 받을 때, 수락한 의뢰 중 가장 높은 비용을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n, k, res;

int arr[100010];

multiset<int> ms;

int main() {
    // 입력
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < k; i++) {
        ms.insert(arr[i]);
    }

    // 초기 k개 의뢰 중 최소 비용
    res = max(res, *ms.begin());

    // 모든 연속한 k개 의뢰 중 최소 비용 탐색
    for (int i = k; i < n; i++) {
        int left = arr[i - k];
        int right = arr[i];

        ms.erase(ms.find(left));
        ms.insert(right);

        res = max(res, *ms.begin());
    }

    cout << res;

    return 0;
}

---

코드 설명

슬라이딩 윈도우 방식을 이용한다.

 

연속한 k개 자연수, arr[left]부터 arr[right]까지를 하나의 윈도우로 생각하고 왼쪽에서 오른쪽으로 이동하면서 해당 윈도우의 최솟값을 파악한다.

 

이 때, 가장 왼쪽 원소(arr[left])와 가장 오른쪽 원소(arr[right])만 변화하므로, 두 원소만 체크한다.

 

방법은 여러가지가 있을 수 있지만, MultiSet을 이용한다.

(Set과 비슷하지만, 중복된 원소를 허용하는 자료구조)

---

고찰

MultiSet은 set 헤더를 추가해야 사용 가능하다.

#include <set>

 

- 빈 MultiSet 생성 

multiset<int, greater<int>> ms; // (default는 오름차순)

 

- MultiSet에서 원하는 원소의 iterator 반환(찾기)

ms.find(num);

 

- MultiSet에서 해당 iterator의 원소 삭제

ms.erase(it);

 

- MultiSet에서 원소 삽입

ms.insert(num);

 

맨 앞, 맨 뒤 원소 접근

// iterator 반환
ms.begin();
ms.end();

// iterator에 해당하는 원소 반환
*ms.begin();
*ms.end();