[일반] 이분탐색 관련 질문한개만..

[코프링(124.56)]

풀이가 최대값을 배열의 모든합으로 잡은 후에

k block만큼 나눌 수 있는지를 기준으로 이분탐색을 하는건데

여기서 이해가 안가는점이 mid값이 배열에 없는 숫자일 수도 있는데

어떻게 정답이 나오는건가요??

이분탐색을 계속하다가 100%에 도달하면 결국 정답이 나올 수 밖에없다는데

와닿지가 않아서..

[캐티(tae826)]

어차피 이분탐색이 가능하려면 가능한 답이 연속해야함. n 이상의 모든 답은 가능 or n 이하의 모든 답은 가능 이런 식으로. 그렇기 때문에 n이라는 값을 배열에 있는 숫자들로 못 만들어도 n이 가능하면 결국 n보다 작고 배열에 있는 숫자들로 만들 수 있는 어떤 m으로 가능함

[캐티(tae826)]

좀 어렵게 설명이 써지는데,, 아무튼 답 이상의 모든 값에 대해서 이 답이 가능한가요? 알고리즘이 yes를 말하기 때문에 결국에 이분탐색을 하다보면 답을 찾을 수 밖에 없다는 얘기

[코프링(124.56)]

위 문제에서 만약 mid값 20이고 k block안에 20이 된다고해도 20이하인 19는 배열안에 19가 없으면 답이 안될텐데.. 이해가 좀 안가네용

[캐티(tae826)]

저 결정문제는 "블록 안의 값 합이 X 이하일때 가능한가?" 임. "블록 안의 값이 정확히 X일때 가능한가?" 면 님 말대로 오류가 있는게 맞는데 이하이기때문에 저 결정문제에 대한 답이 연속적이고 내 말이 되는거

[캐티(tae826)]

값이 19가 가능하면 20도 당연히 가능함 ㅇㅇ. 합이 20이하인 그룹들로 K개를 만드는 것이 가능한가? 이니까 합이 19 이하인 그룹으로 K개를 만드는게 가능하면 20도 당연히 가능하지

[aaaaaa(219.248)]

19이하인 값으로 가능하면 더 내려갈거고 19가 불가능하면 20에서 멈추겠죠 딱 그값을 찾는게 아니라 최댓값이 그 값 이하인 k분할 가능하냐? 를 판단하는거니까 - dc App

[코프링(124.56)]

아 제가 문제를 조금 잘못봤네요 합이니까 배열에 숫자랑 상관이없구나; 죄송합니당;