[백준] 31741. 구간 덮기

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

문제 요약

• 구간 S-E가 주어짐(1 ~ 10^9)
• 선분 N개가 주어짐(N=10^6)
• 선분을 최대 3개 이용해서 구간을 덮을 때 최소 오차 구하기
• 오차 = 사용하는 선분간 겹치는 길이
• 점이 같아도 겹치는 것, 덮는 것으로 인정
  • (1,2) (2,3) 선분은 겹침
  • (2,3) (2,3) 은 덮임

접근법

• 선분 하나로 덮을 수 있는지 판단 : 쉬움
• 선분 두개로 덮을 수 있는지 판단
  • 오른쪽 선분의 후보를 구하고(끝점 이후에 있는지)
  • 왼쪽 선분을 구하고(시작점 이전에 있는지)
  • 왼쪽 선분의 끝점보다 작거나 같은 것중에 가장 큰 오른쪽 선분 구하기
  • 오른쪽 선분이 내림차순 정렬되어있다고 치면 왼쪽 값들은 모두 작거나 같을 것이고 그 중에 가장 큰 것 구하기
  • <=, <=, <=, ......, <=(바로 여기) , <
  • upper_bound를 이용하면 upper_bound의 바로 이전 지점임
• 선분 세개로 덮을 수 있는지 판단
  • 중간선분을 찾은 후 선분 두개 아이디어를 사용
  • 왼쪽 선분의 후보, 오른쪽 선분의 후보를 구함. 내림 차순 정렬
  • 중간 선분이 될 후보들을 시작점 기준으로 내림 차순 정렬
  • 어떤 중간 선분이 왼쪽 선분 A, B, C, D에 모두 쓰일 수 있다면(겹칠 수 있다면) 그중 끝점이 가장 작은 것에 쓰이는 것이 유리함
  • 아래 예시에서 보면 중간선분은 A에서 가장 적게 겹치고 이후로 갈수록 겹치는 범위가 늘어남

  예시
  중간선분 :                              =====================================
  A       :      ---------------------------
  B       : ----------------------------------------
  C       :                       --------------------------
  D       :          -----------------------------------------------

  • 적절한 중간 선분을 골랐다면 오른쪽 선분 후보중에서 중간 선분의 끝점보다 작거나 같으면서 가장 큰 시작점을 같은 선분을 고름(upper_bound 이용)
  • 다음번 중간 선분은 이 다음것부터 탐색함 (물론 매번 이분 탐색을 통해 찾아낼 수도 있음)