백준 2905번 홍준이와 울타리

문제 링크입니다: https://www.acmicpc.net/problem/2905

monotone priority queue(https://en.wikipedia.org/wiki/Monotone_priority_queue)을 이용해 푸는 문제였습니다.

간단히 설명하자면, 우선순위 큐를 이용하여 최소힙을 구현하는데 최소힙 내 요소들이 감소하지 않고 증가해야한다는 것입니다. 

그래도 설명이 모호하다면 슬라이딩 윈도우 기법인데 슬라이드 내 최소값을 찾는 문제라고 생각하면 될 것 같습니다.

코드는 http://codersbrunch.blogspot.com/2016/02/2905.html를 참고했습니다.

알고리즘은 아래와 같습니다.

1. 우선 높이를 다 입력받고 높이의 누적합을 저장합니다.

2. 인덱스와 높이를 저장하는 덱을 선언하여 인덱스 [0, X - 1] 범위 내 monotone 우선순위 큐를 구현합니다.

-> 첫 페인트칠을 위해

3. 이후에는 [X, N] 범위 내 반복문을 수행합니다.

i) 항상 monotone 우선순위 큐를 유지합니다.

ii) 칠할 높이가 달라지면 현재 인덱스 전까지의 범위를 칠해주고 붓질한 횟수를 계산하고 새로운 높이와 밑변의 시작 인덱스를 업데이트해주고 칠한 범위만큼 누적합에서 빼줍니다.

iii) 범위를 초과해서 칠할 수 없기 때문에 붓질은 인덱스 (i - X)까지 칠할 수 있습니다.

a) 현재 덱의 front에 있는 인덱스를 저장하고 pop을 해줍니다.

b) 만약 a)에서 pop한 front의 높이가 현재 덱의 front 높이와 다르다면 ii)처럼 진행해줍니다. (기존 밑변이 a)에서 저장한 인덱스까지였으므로 새로운 밑변의 시작은 [a)에서 저장한 인덱스 + 1] 입니다)

4. 칠해지지 않은 부분과 붓질한 횟수를 출력해줍니다.

#include <iostream>

#include <deque>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N, X;

int height[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> X;

 

        long long area = 0;

        for (int i = 0; i < N; i++)

        {

                 cin >> height[i];

                 area += height[i];

        }

 

        deque<pair<int, int>> dq; //idx, height

        //monotone priority queue

        for (int i = 0; i < X; i++)

        {

                 while (!dq.empty() && dq.back().second > height[i])

                         dq.pop_back();

 

                 dq.push_back({ i, height[i] });

        }

 

        int tempHeight = dq.front().second; //칠할 높이

        int result = 0;

        int idx = 0; //밑변 범위를 위해

        //페인트질 시작

        for (int i = X; i <= N; i++)

        {

                 //monotone priority queue

                 while (!dq.empty() && dq.back().second > height[i])

                         dq.pop_back();

 

                 dq.push_back({ i, height[i] });

                

                 //현재 인덱스부터는 새로운 높이로 칠한다는 뜻

                 //따라서 i ~ (idx - 1)까지 기존 높이로 칠해주고 높이 업데이트

                 if (tempHeight != dq.front().second)

                 {

                         result += (i - idx - 1) / X + 1;

                         area -= (long long)(i - idx) * tempHeight;

                         idx = i;

                         tempHeight = dq.front().second;

                 }

 

                 //붓질은 i - X일 때 마지막으로 할 수 있다

                 if (dq.front().first <= i - X)

                 {

                         int curIdx = dq.front().first;

                         dq.pop_front();

 

                         if (tempHeight != dq.front().second)

                         {

                                 result += (curIdx - idx) / X + 1;

                                 area -= (long long)(curIdx - idx + 1) * tempHeight;

                                 idx = curIdx + 1;

                                 tempHeight = dq.front().second;

                         }

                 }

        }

 

        cout << area << "\n";

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~