예제 입력
9 3 // 강의 9개 , 블루레이 3개
1 2 3 4 5 6 7 8 9 // 각 강의마다 기타 레슨의 길이
예제 출력 17
블루레이 3개에 각각 1 2 3 4 5 / 6 7 / 8 9 씩 들어간다. 블루레이는 모두 같은 크기이어야 하므로 최소 크기는 17이 된다. 이 문제는 블루레이의 최소 크기를 찾는 문제이다. 빠르게 탐색하기 위해서 우리는 이분탐색을 사용할 수 있다.
| 이분탐색(Binary Search)이란?
: 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다.
- 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 버위를 반으로 줄인다.
- 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다.
- 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이분 탐색ㅇ다.
- 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.
ex) 영어 사전에서 단어를 찾는 과정과 동일하다. 영어 사전을 펼쳐서 찾고자 하는 단어가 현재 페이지에 있는 단어보다 앞에 있는지, 뒤에 있는지 결정한 다음, 단어가 있는 부분 만을 다시 검색한다.
| 이분 탐색의 구현
1. 탐색의 대상이 되는 자료들이 array[left] 에서부터 array[right]에 들어있다고 가정하자
즉 어떤 시점에서 탐색되어야 할 범위는 left에서 right까지가 된다.
맨 처음 left에는 0번 인덱스의 값, right에는 n-1번 인덱스의 값이 들어가 있을 것이다.
2. left와 right값에 의거해 중간값 mid 값은 (left+right)/2 이다.
3. array[mid] 값과 구하고자 하는 key 값을 비교한다.
3-1. key > mid : 구하고자 하는 값이 중간값보다 높다면 left를 mid+1로 만들어 준다. (왼쪽 반을 버림)
3-2. key < mid : 구하고자 하는 값이 중간값보다 낮다면 right를 mid-1 로 만들어 준다.(오른쪽 반을 버림)
3-3. key==mid : 구하고자 하는 값을 찾음 중간값 리턴
4. left > light 가 될 때까지 1~3번을 반복하면서 구하고자 하는 값을 찾는다.
| 접근 방법
1. 강의는 순서대로 들어가야 하므로 정렬하지 말아야 한다.
2. 임의의 블루레이 크기를 정하여 담아 본 다음, 블루레이 갯수가 인풋에서 제한한 갯수보다 많아지면 블루레이 크기를 늘려야겠고, 적어지면 블루레이 크기를 줄이면 된다. --> 이 부분을 이분 탐색하자!
ex) 블루레이 크기 10
{1,2,3,4},{5},{6},{7},{8},{9} = 총 블루레이 갯수 6개됨
--> 블루레이 크기를 키워야겠다!
3.이분탐색에서 left, right를 정해야 한다.
1) right
제일 극단적인 끝값은 모든 레슨의 길이를 더한 값이 된다.
ex) 1 2 3 4 5 6 7 8 9 의 인풋을 다 더하면 45이다. 블루레이 하나의 크기가 45라면 블루레이 1개에
모든 레슨을 다 담을 수 있다.
2) left
블루레이 하나의 크기가 만약 1이었을 경우, 레슨 1만 담을 수 있고 나머지는 모두 담을 수 없다. 이러면 문제의 조건에 어긋나게 된다. 모든 레슨들을 블루레이에 담아야 하기 때문이다. 따라서 레슨 중 크기가 가장 큰 값이 왼쪽 끝 값이 되어 야 할 것이다.
--> Math.max 함수 사용해서 숫자 집합중 가장 큰 수 찾기.
4. 반복문을 돌려서 레슨의 길이를 더하는데, 더한 값이 left와 right의 중간값인 mid보다 클 경우, count를 하나 올려준다.
ex) mid가 16인 경우
1 2 3 4 5 6 7 8 9 // 1,2,3,4,5,6 -->21 이므로 count 1 추가.
{1,2,3,4,5} {6,7} {8} {9} 총 블루레이 갯수 4개가 나온다. 블루레이 크기를 키우자~ 판별 가능.
만들어야 하는 블루레이 갯수와 비교하여 큰지 작은지 판별하기 위해 count 변수가 필요하다.
| 입력,출력
bufferedReader 로 입력값을 받고 println 을 사용하여 출력했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Guitar_2343 {
static int N, M;
static int[] lesson;
static int left, right;
public static void main(String[] args) throws IOException{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//ex) {1,2,3,4,5,6,7,8,9}
//강의 수 N , 블루레이 갯수 M , 각 강의의 길이 배열 lesson 초기화
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lesson = new int[N];
st = new StringTokenizer(br.readLine()," ");
int sum = 0;
for (int i = 0; i < N; i++) {
lesson[i] = Integer.parseInt(st.nextToken());
sum += lesson[i];
left = Math.max(left, lesson[i]); //9
}
right = sum; //45
System.out.println(binSearch(left,right));
}
public static long binSearch(long left, long right) {
while(left <= right) {
long sum = 0;
long mid = (left+right)/2;
int count = 1;
for (int i = 0; i < N; i++) {
sum += lesson[i];
if(sum > mid) {
sum = lesson[i];
count ++;
}
}
//필요한 블루레이 갯수가 M보다 작거나 같으면
if(count <= M) {
right = mid - 1;
}
//총 필요한 블루레이 개수가 M보다 크다면
else {
left = mid +1;
}
}
return left;
}
}