문제 바로가기
https://www.acmicpc.net/problem/2512
문제 소개 및 재정의
총 예산 M이 주어졌을때 N개의 예산요청을 처리할수 있는 예산 상한액 K를 찾으시오.
K중에서 N개의 예산요청 처리후 집행하는 총 예산이 M과 가장 가깝게 하는 K를 구하시오.
예산 집행 규칙.
K이하의 예산요청(smaller)은 smaller의 값을 그대로 집행.
K를 초과하는 예상요청(bigger)는 예산 상한액인 K의 값으로 집행.
문제 패턴
고정된 크기 K에 N개의 아이템을 넣어야 할때 최적의 K값을 찾으시오. => 이진 탐색
O(K*N) = 10^9 = 10억 일때 => 아주 큰 규모 => 이진 탐색
어떻게 풀까? - 이진 탐색
포인트
먼저 이진탐색을 구현하고, 탐색 방향을 결정할 로직을 결정한다.
탐색 방향 결정할 로직 구현 후 어떤 방향에 매핑해야 될지 잘 모르겠다면, BruteForce하게 대입해봐도 괜찮다.
true - false
false - true
대입 후 프린트를 찍어보면 문제를 더 빠르고 정확하게 풀 수 있다.
정확도와 안정성이 중요한 작업이라면 신중하게 한번에 정답을 찾아야 하겠지만, 시험볼때는 위의 것들과 더불어 속도가 생명이다.
BruteForce를 사용할 수 있는 환경이라면 과감하게 사용하자.
대부분의 연구는 실험 결과를 토대로 가설을 검증한다.
그런면에서 나쁘지 않은 방법이다.
코드
이진 탐색
//// 이진탐색
static void bs(int start, int end) {
// 바닥 조건
if(start>end)
return;
// 재귀 파트
int mid = (start+end)/2;
if(isOK(mid)) {
bs(start,mid-1);
} else {
best = mid;
bs(mid+1,end);
}
}탐색 방향 결정 로직
static boolean isOK(int mid) {
int sum = 0;
for(int i=0; i<N; i++) {
if(origin[i]<=mid)
sum+=origin[i];
else //origin[i]>mid
sum+=mid;
}
// 순회 종료
if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
return false;
} else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
return true;
}
}전체코드 - 정렬 버전
보통 이진탐색하면 아이템이 정렬되어야 하는 경우가 많다.
따라서 일단 정렬시키고 문제를 풀어보았다.
이 경우 장점
- 생각할게 적어진다.
- 이진탐색범위의 끝값을 찾기 위해서 MAX값을 찾아야 하는데 정렬하면 손쉽게 찾을수 있다. 코드 라인 감소
import java.util.*;
import java.io.*;
public class BOJ_2512_예산 {
// 입력 고정
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens;
static StringBuilder outpur = new StringBuilder();
// 세팅
static int N;
static int[] origin;
static int M;
static int best;
// 메소드
//// 이진탐색
static void bs(int start, int end) {
// 바닥 조건
if(start>end)
return;
// 재귀 파트
int mid = (start+end)/2;
if(isOK(mid)) {
bs(start,mid-1);
} else {
best = mid;
bs(mid+1,end);
}
}
static boolean isOK(int mid) {
int sum = 0;
for(int i=0; i<N; i++) {
if(origin[i]<=mid)
sum+=origin[i];
else //origin[i]>mid
sum+=mid;
}
// 순회 종료
if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
return false;
} else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
return true;
}
}
// 메인
public static void main(String[] args) throws Exception {
// 입력
N = Integer.parseInt(input.readLine());
origin = new int[N];
tokens = new StringTokenizer(input.readLine());
for(int i=0; i<N; i++) {
origin[i] = Integer.parseInt(tokens.nextToken());
}
M = Integer.parseInt(input.readLine());
// 세팅
Arrays.sort(origin);
// 작업
bs(0,origin[N-1]);
// 출력
System.out.println(best);
} // 메인 종료
}전체 코드 - 정렬 안한 버전
하나의 박스에 여러개의 아이템을 넣는 경우가 있을 경우
고정된 순서로 정렬이여야 하거나, 아니면 오름차순으로 정렬이여야 한다.
하지만 이 문제처럼 하나의 박스에 1개의 아이템만 들어가는 경우에는 순서는 고려대상이 아니다.
하나의 박스에 하나의 아이템이 들어갈수 있냐 아니냐만 고려대상이기 때문이다.
문제해결 후 리뷰중, 정렬할 필요가 없다는 사실을 깨닫고 정렬없이 푼 버전이다.
범위를 지정하기 위해 max값을 별도로 찾아야 할 필요가 있었다.
코드상에서 차이는 딱 그거 하나다.
import java.util.*;
import java.io.*;
public class BOJ_2512_예산 {
// 입력 고정
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens;
static StringBuilder outpur = new StringBuilder();
// 세팅
static int N;
static int[] origin;
static int M;
static int best;
// 메소드
//// 이진탐색
static void bs(int start, int end) {
// 바닥 조건
if(start>end)
return;
// 재귀 파트
int mid = (start+end)/2;
if(isOK(mid)) {
bs(start,mid-1);
} else {
best = mid;
bs(mid+1,end);
}
}
static boolean isOK(int mid) {
int sum = 0;
for(int i=0; i<N; i++) {
if(origin[i]<=mid)
sum+=origin[i];
else //origin[i]>mid
sum+=mid;
}
// 순회 종료
if(sum<=M) { // 예산승인 가능. 예산 상한액 증감 가능.
return false;
} else { // sum>M ==> 예산 초과됨. 예산 상한액 삭감
return true;
}
}
// 메인
public static void main(String[] args) throws Exception {
// 입력
N = Integer.parseInt(input.readLine());
origin = new int[N];
tokens = new StringTokenizer(input.readLine());
int max = 0;
for(int i=0; i<N; i++) {
origin[i] = Integer.parseInt(tokens.nextToken());
max = Math.max(max, origin[i]);
}
M = Integer.parseInt(input.readLine());
// 세팅
// 작업
bs(0,max);
// 출력
System.out.println(best);
} // 메인 종료
}퍼포먼스
정렬 버전 [
14_104 KB|108 ms]
정렬X 버전 [
13_076 KB|92 ms]
퍼포먼스에서 유의미한 차이는 안 보인다.
마무리
BruteForc한 시도를 할 수 있는 환경이라면 꼭 하자!
