가능한 mid 값 중 최대값(upperbound)을 찾아야 해서요.
5 3
1 2 3 4 7
위 예제로 예를 들어볼게요.
만약에 최대 거리를 찾아야 한다는 조건이 없다고 생각해 봅시다.
이분탐색이 아닌 부르트포스로 house[0]부터 house[N-1]까지 하나하나 가능한 값을 찾으면
[1,2,3] 거리 1
[1,3,7] 거리 2
[1,4,7] 거리 3
만약 최대 거리를 찾아야 하는 조건이 없다면 이렇게 거리1, 2, 3이 가능한 값이에요.
하지만 문제는 최대 거리를 찾아야 하기 때문에 가능한 값 중 최대값인 거리3이 정답이 됩니다.
거리 1과 2는 조건이 없다면 가능한 답이지만 거리 1이나 2만큼 설치하면 공유기를 C개 이상 설치가 가능해요. (최대값이 아님)
거리 4는 공유기를 2개밖에 설치할 수 없으니 조건이 없어도 가능한 답이 아니에요. (불가능)
최종적으로 이분탐색이 끝났을 때 가능한 답 중 최대값, 즉 가능한 답 중 upperbound가 right이기 때문에 right을 그래로 출력해도 됩니다.
저 코드는 iptime_cnt < C로 upper bound를 구하는 코드에요.
hellowfriend 1년 전 1
제가 이 문제를 푸신 다른 분의 코드를 참고하고 있었는데요,
여기서 If( iptime_cnt >= C) 일 때마다, mid로 최적값을 갱신시키셔 마지막에 최적값을 결과로 출력하는 방법이 아니라,
그냥 right값을 결과로 출력하는 방법을 사용하셨더라고요.
저는 보자마자 right를 쓰면 항상 최적값이 나올거라고 떠올리기 쉽지 않아서
왜 right값이 항상 최적값으로 나오는 지 직접 마음속으로 설명해 보려고 하니,
while문이 iptime_cnt >= C로 끝날 때는 right = mid 이므로 바로 이해할 수 있는데,
while문이 iptime_cnt < C로 끝날 때는 좀 돌아가는 느낌이 강해서요.
두번째 경우도 직관적으로 설명이 가능한가요?
제가 너무 주관적인 질문을 한다고 느끼셨다면 양해부탁드립니다.
저의 무지로는 어떻게 저렇게 생각했는 지 접근법이 궁금하더라고요.