백준 31741 구간 덮기

문제

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

풀이

• 쉬운 문제 가정

  • 2개만을 이용해 구간을 덮는 문제의 풀이
  1. 선분을 2개로 나눈다.
     a. 시작점이 S이하인 선분을 담는 배열 A
     b. 끝점이 E이상인 선분을 담는 배열 B
  2. A를 순회하며 B에서 이분 탐색으로 다음을 찾는다.
     • 이분 탐색을 위해 B를 시작점을 기준으로 정렬한다.
     • B의 시작점이 A의 끝점 이하인 선분 중 시작점이 제일 큰 선분 = B에서 시작점이 A 초과인 선분의 바로 전 인덱스 선분 찾기
  • 이를 통해 오차의 최솟 값을 구할 수 있다.
  • 이는 B를 순회하며 A에서 이분 탐색으로 A의 끝점이 B의 시작점 이상인 선분 중 끝점이 제일 작은 선분을 찾는 것으로도 풀 수 있다.

• 원래 문제로 돌아가기

  1. 추가적인 선분 분류를 만든다.
     • 시작점이 S초과고 끝점이 E미만인 선분을 담는 배열 C
  2. C에서 쉬운 문제에서 가정한 두가지 풀이를 융합할 수 있지 않을까?
     • C는 사이에 있는 선분이므로 A의 끝점이 C의 시작점 이상인 선분 중 끝점이 제일 작은 선분 찾기
       • 이는 lower bound를 이용해 찾을 수 있다.
     • 마찬가지로 B의 시작점이 C의 끝점 이하인 선분 중 시작점이 제일 큰 선분 찾기
       • 이는 uppder bound를 이용한 뒤 찾은 인덱스를 1빼주면 된다.
     • 왜냐하면 C를 순회하며 C에서 현재 보고있는 선분을 기준으로 A와 B에서 오차가 제일 작은 선분을 찾는다면, A와 B사이의 오차 역시 최소이기 떄문이다.(0일수도 있다.)