https://www.acmicpc.net/problem/17976
문제 요약
- 시작점, 길이를 갖는 thread가 x축위에 배치되어 있음
- 서로 포함관계는 없음
- thread위에 점 한개를 찍음(knot라고 표현)
- 이렇게 찍은 점들간의 거리중에 가장 작은 값이 있을텐데, 그 값을 가장 크게 만들기
접근법
- 작은값을 크게 문제라서 일단 파라메트릭 서치로 접근함
- 일단 thread끼리 포함은 안되니까 편하게 시작 점으로 정렬시킴 => 시작점이 겹치지는 않을 것임
- 점을 찍어보는데 제한을 걸어봄 : 가장 가까운 거리가 k이상으로 구성이 되는지 안되는지
- 구성이 되면? k를 더 키워본다. 안되면? k를 줄인다
- 왜냐면 잘은 모르겠지만 간격이 1이면 구성이 되긴 됨
- 여기서 파라메트릭 서치의 용어정리를 잘 해야함
- 확인하고자 하는 값 k를 가지고서 만들다보니
- k보다 작게 만들어야한다면?? => k는 사용 못함
- k로 만들수 있다면?? => 사용 가능
- k보다 크게 만들어야한다면?? => 일단 k는 된다고 봐도됨. k값을 늘려서 더 확인해볼테니까
newbieski