문제
문제점 해결
해당 문제는 이분탐색으로 풀 수 있는 문제였다. 프로그래머스 코딩테스트 고득점 Kit 中 이분탐색 문제 모음집에 있는 입국심사와 징검다리 문제를 풀지 못해 구글에 검색해 풀이를 보며 이분탐색을 공부하다보니 직접 풀만한 문제를 찾던 중 발견한 문제이다. 딱 이분탐색이 무엇인지 공부가 많이 된 문제였다.
잘못된 변수 초기값으로 인한 실패
처음 end(최대 예산 금액)을 가장 요청이 적은 값으로 설정해뒀는데 이 부분 때문에 제출할때마다 틀렸다는 결과를 받았다. 모두가 만족하는 예산을 배정하기 위해선 가장 적은 예산 요청 금액을 최대치로 설정해뒀는데 그게 아니라 가장 많은 예상 요청 금액을 최대치로 설정해뒀어야 하는 것이었다.
처음엔 end = city[0] * N으로 설정해서 최대 배정할 수 있는 금액치를 가장 적은 예산 요청 * N(지역 수)로 설정했는데 반례를 찾다보니 오류가 발생함을 알았다.
100
384 387 278 416 294 336 387 493 150 422 363 28 191 60 264 427 41 427 173 237 212 369 68 430 283 31 363 124 68 136 430 303 23 59 70 168 394 457 12 43 230 374 422 420 285 38 199 325 316 371 414 27 92 481 457 374 363 171 497 282 306 426 85 328 337 6 347 230 314 358 125 396 83 46 315 368 435 365 44 251 88 309 277 179 289 85 404 152 255 400 433 61 177 369 240 13 227 87 95 40
50000
위와 같은 입력이 들어온다면 가장 적은 예산 요청 6 * 100 으로 600이 end값이 된다.
이 값이 while문에서 처리되면서 의도치 않은 부분에서 while문을 끝내버리는 값으로 바뀌어버리고 올바른 정답이 나오지 않는다.
사실 아직도 이분탐색은 어렵다..ㅠㅠ 하지만 조금씩 감이 잡히는듯하니 관련 문제를 몇가지 더 풀어봐야할것 같다.
풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int answer = 0;
int N = sc.nextInt();
int[] city = new int[N];
for (int i = 0; i < N; i++)
city[i] = sc.nextInt();
int M = sc.nextInt();
Arrays.sort(city);
int start = 0;
int end = city[N-1];
while(start <= end) {
int mid = (start + end) / 2;
int sum = 0;
for (int i : city) {
if(i > mid)
sum += mid;
else
sum += i;
}
if(sum > M)
end = mid - 1;
else {
start = mid + 1;
answer = mid;
}
}
System.out.println(answer);
}
}