1477
-
[백준]1477: 휴게소 세우기 - JAVA문제풀이/백준 2021. 6. 14. 17:29
[백준]1477: 휴게소 세우기 풀이 딱 보자마자 이분탐색을 통해 풀어야 겠다는 생각이 들지 않았어서 풀이하는데 시간이 좀 걸렸다. 이분탐색 유형에 아직 익숙하지 않아서 그런 것 같다. 이 문제는 휴게소의 간격을 기준으로 이분탐색을 진행한 다음 해당 간격이 형성되도록 M개의 휴게소를 생성할 수 있을 때의 최소값을 찾는 문제이다. 예제 입력1을 예시로 살펴보자. 휴게소가 설치될 수 있는구간은 다음과 같다. 1 ~ 81 83 ~ 200 202 ~ 410 412 ~ 554 556 ~ 621 623 ~ 754 756 ~ 799 휴게소의 위치와 0, L을 포함한 값을 배열에 담아 정렬시켜준다. (범위 값 계산을 하기 위해) 이때, 휴게소 간격의 최소값은 0, 최대값은 L이 된다. 이제 이분 탐색을 시작한다. 탐색..