#1276 교각 놓기(정렬)

이번 문제는 Gold V 등급 난이도라고 되어 있지만, 문제 자체는 아주 쉽습니다.  영어가 제공되는 문제들의 특징들이 문제가 명확하게 설명되어서, 굳이 한글이 번역되지 않은 문제라도 풀만합니다.

 

2차원상에 다리가 있는데, 이 다리에 교각을 놓으려고 합니다.  다리 밑에 다른 다리가 있는 경우 거기까지만 교각을 세우면 됩니다.  이 때 교각의 총 길이를 계산하면 됩니다.

 

예를 들어서 다음과 같이 다리가 있다고 해보죠.

 

왼쪽 그림에서 총 다리가 3개가 있는데, 이 다리에 교각을 내려놓으면, 다른 다리에 얹히는 경우 실제 다리 높이보다 짧은 길이의 교각을 세우게 됩니다.  그렇게 해서 만들어진 교각이 오른쪽 그림입니다.

 

영어 문제에서는 다리가 서로 겹쳐있지 않다고 했으니까, 예외를 생각하지 않아도 됩니다.  서로 겹쳐있는 경우라면, 어떤것이 더 위에 있는가로 잡느냐에 따라서 결과가 달라지게 됩니다.

 

풀이방법은 간단합니다.  다리의 갯수가 최대 100개이므로, 전체를 검색해도 상관이 없습니다.  전 일단 정렬부터 했습니다.  다리 높이에 대해서 정렬한 다음, 검사할 다리 높이보다 낮은 다리들에 대해서 검사를 하면 됩니다.  단 밑에 다리가 없는 경우에는 다리의 구조체를 사용할 수 없으므로, 예외를 만들지 않게하기위해서 다리에 대해서 일단 교각을 땅까지 내리는 것으로 한 후, 다리가 겹치는 경우 그 높이만큼 빼주면 예외를 처리할 필요가 없습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1276 - PLATFORME
//    - by Aubrey Choi
//    - created at 2020-01-14
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Bridge { int y, x1, x2; } b[100];
int main()
{
  int n, i, j, r=0;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d%d%d",&b[i].y,&b[i].x1,&b[i].x2);
  std::sort(b,b+n,[](Bridge &a, Bridge &b){return a.y>b.y;});
  for(i=0;i<n;i++)
  {
    r+=2*b[i].y; int x1=b[i].x1, x2=b[i].x2-1;
    for(j=i+1;j<n;j++) if(x1>=b[j].x1&&x1<b[j].x2){r-=b[j].y; break;}
    for(j=i+1;j<n;j++) if(x2>=b[j].x1&&x2<b[j].x2){r-=b[j].y; break;}
  }
  printf("%d\n",r);
}