[BAE/<JOON> 문제풀이] 12929. 빌딩 높이

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

12929번: 빌딩 높이

서론

 

파라메트릭은 뭘 근거로 이 문제가 파라메트릭이라고 판정을 하는걸까 ?

그냥 앞으로 무슨 문젠지 모르겠으면 파라메트릭으로 상정을 해야겠다.

이 문제는 태그 보고 풀었다.

---

풀이

빌딩 높이로 파라메트릭 하면 됨. 각 지점마다 빌딩 높이 제한을 설정해야 한다.

모든 지점의 높이 제한을 지키는 빌딩의 최고 높이를 찾는 것이 목적이므로 마지막 빌딩도 가상의 지점으로 추가하는 것이 여러모로 편하다. 단, 문제에서 주어진 마지막 지점 위치가 n번째 빌딩이 아닌 경우에만 추가해야 한다.

 

지점의 높이 제한이 그 지점의 진짜 최댓값이 아닐 수 있다. 옆 지점 빌딩 ( [i - 1], [i + 1] ) 까지의 거리가 충분히 가깝고 빌딩 차이 제한 ( k ) 가 충분히 작다면 i 번째 지점의 높이 제한보다 더 낮은 높이로 쌓도록 강제되는 경우가 있을 수 있다.

즉 양쪽 지점에서 영향을 받아 높이 제한이 달라지므로 이런 지점들을 미리 검사해서 각 지점마다 진짜 높이 제한을 계산하고 파라메트릭을 돌려야 한다.

 

파라메트릭 판정은 아래와 같다.

현재 예상 빌딩 최고 높이 : h

현재 지점 ( i 번째 지점 ) 빌딩 위치 : arr[i].p

현재 지점 ( i 번째 지점 ) 높이 제한 : arr[i].h

인접한 빌딩 간의 차이 제한 : k

지점의 개수 : m

 

예상한 빌딩 최고 높이가 가능하기 위해서는 각 지점마다 정해진 최고 높이를 위배하지 않는지 여부를 검사해야 한다.

그림으로 나타내면 아래와 같다.

이해를 돕는 그림

주어진 k로 목표 높이와 건물의 높이의 차를 구하면 해당 높이에 도달하기 위해 필요한 최소 건물 개수를 알 수 있다.

0 <= i < m 인 모든 i에 대해 (i번째 지점에서 필요한 건물 수와 i + 1번째 지점에서 필요한 건물 수의 합) 이 두 지점 사이 건물수보다 적다면 가능한 것으로 판정할 수 있다. 

---

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
using ll = unsigned long long;
struct bl {
    ll p, h;
};
vector<bl> arr;
ll n, k, m;
bool ch(ll h) {
    for (int i = 1; i <= m; i++) {
        if (arr[i].h > h || arr[i - 1].h > h) return true;
        ll d1 = (h - arr[i].h) / k + ((h - arr[i].h) % k == 0 ? 0 : 1);
        ll d2 = (h - arr[i - 1].h) / k + ((h - arr[i - 1].h) % k == 0 ? 0 : 1);
        if (d1 + d2 <= arr[i].p - arr[i - 1].p) return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k; 
    cin >> m; arr = vector<bl>(m + 1);
    arr[0] = { 1, 0 };
    for (int i = 1; i <= m; i++) {
        cin >> arr[i].p;
    }
    for (int i = 1; i <= m; i++) {
        cin >> arr[i].h;
    }
    if (arr[m].p != n) {
        arr.push_back({ n, arr[arr.size() - 1].h + (n - arr[arr.size() - 1].p) * k });
        m++;
    }
    for (int i = 1; i <= m; i++) {
        ll s1 = arr[i - 1].h + (arr[i].p - arr[i - 1].p) * k;
        arr[i].h = arr[i].h < s1 ? arr[i].h : s1;
    }    
    for (int i = m - 1; i >= 1; i--) {
        ll s1 = arr[i + 1].h + (arr[i + 1].p - arr[i].p) * k;
        arr[i].h = arr[i].h < s1 ? arr[i].h : s1;
    }
    ll f = 1, r = k * n; ll d = f; 
    while (f <= r) {
        ll mid = (f + r) / 2;
        if (ch(mid)) {
            f = mid + 1; d = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << d;
    return 0;
}