BOJ 1276 - 교각 놓기

www.acmicpc.net/problem/1276

1276번: 교각 놓기

 

문제에서 요구하는 것은, 교각의 길이를 최소화 하여 설치하는 방법을 찾는 것 이므로

수평 값(x1, x2) 에 대해서는 별도의 정렬 처리를 해줄 필요가 없고,

수직 값(y) 에 대해서 정렬 처리를 해줄수밖에 없다.

 

수직값을 내림 차순으로 정렬해서 높은 위치에 있는 다리 부터 탐색을 시도하는데,

자신보다 높이가 낮은 다리의 x 좌표 구간에 현재 다리의 x 좌표 구간이 겹치면,

자신보다 높이가 낮은 다리위에 교각을 세울 수 있다는 소리이므로, 그 지점에 세워서 높이를 낮춘다.

만약 x 좌표 구간이 겹치는 자신보다 높이가 낮은 다리가 없으면 땅 바닥에 세워야 한다. 

 

 

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef struct {
    int y;
    int x1;
    int x2;
}Pos;
 
vector<Pos> vec;
 
int n, answer;
 
bool comp(Pos& p1, Pos& p2) {
    return p1.y > p2.y;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        Pos temp;
        int y, x1, x2;
        cin >> y >> x1 >> x2;
        temp.y = y;
        temp.x1 = x1;
        temp.x2 = x2;
        vec.push_back(temp);
    }
    
    sort(vec.begin(), vec.end(), comp);
    
    for (int i = 0; i < n; ++i) {
        answer += 2 * vec[i].y;
        int x1 = vec[i].x1, x2 = vec[i].x2 - 1;
        for (int j = i + 1; j < n; ++j) {
            if (x1 >= vec[j].x1 && x1 < vec[j].x2) {
                answer -= vec[j].y;
                break;
            }
        }
        for (int j = i + 1; j < n; ++j) {
            if (x2 >= vec[j].x1 && x2 < vec[j].x2) {
                answer -= vec[j].y;
                break;
            }
        }
    }
    
    cout << answer;
    
    return 0;
}