교각 놓기
문제 해석
설치해야하는 최소의 교각 길이의 합을 구하는 문제입니다.
N개의 다리가 있고, 각 다리의 양 끝에 교각을 다른 다리 위 or 바닥에 설치합니다.
교각이 다른 교각과 교차하면 안됩니다.
설계(10)
y축 기준으로 정렬 후, 아래의 다리에 교각을 설치할 수 있는지 판단하는 문제입니다.
왼쪽, 오른쪽 교각을 나누어서 순차적으로 아래로 내려오면서 설치 가능 여부를 검토합니다.
여기서 주의할 점은, 왼쪽 교각을 기준으로 포함 범위를 계산할 때, x1 <= x < x2 이어야 합니다.
오른쪽 기준으로는 x1 < x <= x2 이어야 합니다.
시간복잡도는 모든 다리 탐색 O(N) x 교각 설치 여부 검토 O(N) 으로 O(N^2)에 해결이 가능합니다.
구현(20)
코드
#include <iostream>
#include <algorithm>
#define MAXN 100
using namespace std;
struct node{
int y,x1,x2;
bool operator < (const node& a)const{
return y < a.y;
}
};
int ans,N;
node arr[MAXN];
bool is_possible(int x, int x1, int x2, int mode){
if (mode) return x>x1 && x<=x2;
else return x>=x1 && x< x2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 0 ;i <N ;i++){
cin >> arr[i].y >> arr[i].x1 >> arr[i].x2;
}
sort(arr,arr+N);
ans +=arr[0].y*2;
for (int i = 1 ; i < N; i++){
bool flag[2] ={false,};
for (int j = i-1; j>=0; j--){
if (flag[0] && flag[1]) break;
if (!flag[0] && is_possible(arr[i].x1,arr[j].x1,arr[j].x2,0)){
ans += arr[i].y-arr[j].y;
flag[0] = true;
}
if (!flag[1] && is_possible(arr[i].x2,arr[j].x1,arr[j].x2,1)){
ans += arr[i].y - arr[j].y;
flag[1] = true;
}
}
if (!flag[0]) ans += arr[i].y;
if (!flag[1]) ans += arr[i].y;
}
cout << ans <<"\n";
return 0;
}
디버깅
처음에 왼쪽과 오른쪽의 포함범위를 나누어서 생각하지 않았습니다.
제출결과
0 ms
마무리
정렬알고리즘을 활용하는 문제입니다.
범위 체크를 주의해야 합니다.