백준 3015번 분할 정복식 풀이

 

 

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

3015번: 오아시스 재결합

 

1. 본질적으로 히스토그램 문제 (https://www.acmicpc.net/blog/view/12) 와 동일한 알고리즘이다.

   1. 스택 O(N) 분할 정복 O(NlogN) 세그먼트 트리 O(NLogN) 이 가능하다.

2. 스택 풀이는 티스토리 등에 치면 나오니까 참고하면 된다.

3. 세그먼트 트리... 는 할 줄 모른다.

4. 분할 정복

N 명을 한번에 풀기는 짜증나니까, 반씩 쪼개서 각개격파한다.

a번 ~ b번 사람들끼리 서로 볼 수 있는 쌍을 f(a,b) 이라고 정의한다.

f(a,b) = f(a, mid) + f(mid, b) + (어떤 애매한 값)

일 것이다.

어떤 애매한 값은 좌, 우 애매하게 걸쳐 있는 쌍들이다.

이걸 O(n) 만에 푸는 것이 이 문제의 핵심이다.

어떤 애매한 값

• 알고리즘이 히스토그램 문제와 유사하므로, 히스토그램 분할 정복에서 아이데이션을 얻을 수 있다.

https://salepark.tistory.com/7

중앙에서 스와이핑하면서 히스토그램의 최소값을 구해내고 있다.

(자세한 풀이는 종만북에 있다)

같은 방식으로 푼다.

 

관찰을 해 보면, 걸쳐 있는 쌍들은

 

중앙을 중심으로 [증가하는 키] 들만 후보가 될 수 있다.

그러므로, 좌변, 우변을 스윕하면서 증가하는 값들만 벡터에 삽입한다.

 

	vector<long long> leftSlides;
    vector<long long> rightSlides;
    for (auto i = mid - 1; i >= low; i--) {
        if (buffer[i] >= maxMiddleLeft) {
            leftSlides.push_back(buffer[i]);
        }
        maxMiddleLeft = max(maxMiddleLeft, buffer[i]);
    
    }
    
    for (auto i = mid; i<high; i++) {
        if (buffer[i] >= maxMiddleRight) {
            rightSlides.push_back(buffer[i]);
        }
        maxMiddleRight = max(maxMiddleRight, buffer[i]);
    
    }

 

이제 좌변을 순회하면서 쌍들을 구해나갈 것이다.

각각의 좌변마다 대응할 수 있는 우변의 개수를 구하면 된다.

[기준]에 해당하는 오른쪽 쌍은,

[이전] 보다는 키가 큰 오른쪽 값들부터 해서, (그보다 작은 값은 [이전] 이 키가 더 커지므로, 후보가 될 수 없다)

[기준] 보다 처음으로 키가 커지는 오른쪽 값들 까지만 구하면 된다.

그보다 큰 값은 [기준]보다 키가 더 커지므로, 후보가 될 수 없다.

중앙에서부터 실상 포인터를 이동하면서 값을 더해주는 식이 될 텐데,

그걸 드럽게 쓰면 이렇게 된다.

 

 	int currentRightIndex = 0;

    int previousRightIndex = 0;
    long long previousValue = -1;
    for (auto i=0; i<leftSlides.size(); i++) {
        auto leftValue = leftSlides[i];

        while (currentRightIndex < rightSlides.size() && rightSlides[currentRightIndex] <= leftValue) {
           currentRightIndex++;
       }


        while (previousRightIndex < rightSlides.size() && rightSlides[previousRightIndex] < previousValue) {
            previousRightIndex++;
        }

       answer += min(currentRightIndex + 1ll, (long long) rightSlides.size());

        answer -= previousRightIndex;
        if (i + 1 == leftSlides.size()) {
            continue;
        }
            previousValue = leftValue;
    }

 

 

 

전체 코드

http://boj.kr/435845e4dfc448009f82cddbfc33acef