우선 이분 탐색의 조건으로 정확히 M번 인출이라는 것은 불가능합니다
이분 탐색은 답을 기점으로 왼쪽은 조건 불만족, 오른쪽은 조건 만족인 집합이여야 합니다.
그리고 이 문제의 영어 버전인 Farmer John 을 보시면
정확히 M 번의 fijomonths? 를 가진다고 했는데 무조건 남는 돈이 있으면 써야 한다는 뜻이 아니네요.
예를 들어
5 4
100
100
100
100
100
이런 예시에 대해 답은 200을 출력하죠.. 인출은 3번만 해도 되는데..
반면 fijomonths는 {1}, {2,3}, {4,5} 를 포함하는 게 가능합니다.
kdcal035 7년 전
문제의 조건은 "돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다." 입니다.
바이너리 서치로 풀었는데 , 제가 처음 제출한 코드의 일부는 다음과 같습니다.
if (res > m) return search(mid+1, upper);
else
{
if (res == m) ans = min(ans, mid);
return search(lower, mid-1);
}
몇번을 인출해야하는지 계산한 값 res와 m을 비교해 정확히 m번 인출해서 사용할 경우에만 mid원을 정답의 후보로 생각합니다.
하지만 위의 코드는 오답이라 더 고민을 해보다가 혹시나 해서 m번 이하로 인출한 모든 경우를 정답 후보로 생각하니 accept를 받았습니다.
if (res > m) return search(mid+1, upper);
else
{
ans = min(ans, mid);
return search(lower, mid-1);
}
다른 부분은 수정한 부분이 없습니다.