codingismylife   1년 전

요즘에 이분 탐색 문제 위주로 풀고 있는데요, 문제를 풀다 보면 ~의 최솟값의 최댓값, ~의 최댓값의 최솟값 이런 식으로 되어 있는 경우가 많은데 문제 풀 때마다 헷갈려서 처음에 풀었던 문제들을 풀면서 다시 되짚어가고 있습니다

예를 들어 이 문제처럼 ~의 최댓값의 최솟값을 구하라고 하면, 이분 탐색으로 구하는 값을 최댓값으로 놓고 그 중에 최솟값을 구하라는 것인데 만약 구한 휴게소의 개수가 M개 이상이 될 때 길이를 줄여버리면 구간 길이의 최댓값이 짧아짐에 따라 설치할 수 있는 주유소의 개수가 계속 늘어날 것인데, 이는 휴게소를 M개 설치하라는 조건에 위배되기 때문에 자연스럽게 휴게소를 M개 이하로 설치했을 때, 길이를 줄임에 따라서 M개 미만으로 설치했을 경우에도 더 설치할 수 있게 하여 최종적으로 M개를 설치했을 때라는 조건을 맞추기 위함이라고 이해했습니다. 

이런 식으로 이해하는 것이 괜찮은지 궁금합니다! 아직 많이 부족한 것 같습니다 ...

codingismylife   1년 전

감사합니다~~

댓글을 작성하려면 로그인해야 합니다.