🙋🏻♀️이진탐색 사용!
문제분석
블루레이의 크기가 모두 같고, 녹화순서가 뒤바뀌지 않아야 한다는 조건에서 이진탐색 알고리즘을 선택할 수 있다.
보통 이분탐색은 정렬된 곳에서 찾는게 보통인데 해당 문제에서는 강의의 순서가 뒤바뀌면 안된다라고 적혀있다. 따라서 정렬을 하지 않고 블루레이의 길이에 따라 만들어지는 강의의 수를 체크하여 가장 최소의 길이가 되는 블루레이 크기를 구해야한다.
지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단하여, 모두 저장할 수 있다면 크기를 줄이고, 모두 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 최솟값을 알 수 있다.
이진탐색의 시작 인덱스 = 최대 길이의 레슨
이진탐색의 종료 인덱스 = 모든 레슨 길이의 합
('시작인덱스 > 종료인덱스'일 때까지 수행)
- 중앙값 크기로 모든 레슨 저장 가능 : 종료 인덱스 = 중앙값 -1
- 중앙값 크기로 모든 레슨 저장 불가능 : 시작 인덱스 = 중앙값 + 1
슈도코드
N M 입력받기
A배열 (정렬할 배열)
for(N만큼 반복) {
A에 데이터 삽입
시작 인덱스 저장 (A배열 중 최댓값)
종료 인덱스 저장 (A배열의 총합)
}
start (시작 인덱스)
end (종료 인덱스)
while(start <= end) {
mid = (start + end) /2
sum(레슨 합)
count(현재 사용한 블루레이 개수)
for(N의 개수만큼 반복하기) {
만약 sum + 현재 레슨 시간 > 중간 인덱스
count++
sum = 0
sum에 현재 레슨 시간값 더하기
}
sum이 0이 아니면 마지막 블루레이가 필요하므로 count++
if(count > M : 중간 인덱스값으로 모든 레슨 저장 불가능) {
start = mid + 1
}
else(중간 인덱스 값으로 모든 레슨 저장 가능) {
end = mid -1
}
시작 인덱스 출력
}제출코드
import java.util.Scanner;
public class Main {
public static int[] A;
public static int[] videoSize;
public static int sum;
public static int count;
public static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = new int[N];
int start = 0;
int end =0;
for(int i=0; i<N; i++) {
A[i] = sc.nextInt();
if(start < A[i]) start = A[i];
end = end + A[i];
}
while(start <= end) {
int middle = (start + end)/2;
int sum =0;
int count =0;
for(int i=0; i<N; i++) {
if(sum + A[i] > middle) {
count++;
sum =0;
}
sum = sum + A[i];
}
if(sum != 0) count++;
if(count > M) start = middle +1;
else end = middle -1;
}
System.out.println(start);
}
}헷갈렸던 부분
-
풀이를 보면, 왜 정렬을 하지않고 이진탐색을 쓰나?
원래 이진탐색은 정렬된 데이터에서 사용해야하지만, 이 문제는 조건에 강의의 순서가 뒤바뀌면 안된다는말이 있기때문에, 그대로 사용하면된다.
-> 배열 A가 아닌, 블루레이의 최소 시간을 구하는 start, end, middle 이렇게 3개의 변수 가 정렬된 배열의 인덱스라고 생각하고 푸는 로직이기때문에 가능하다. -
'시작 인덱스 > 종료 인덱스 조건을 만족할 때 탐색을 종료하고, 그때 시작 인덱스가 문제 조건을 만족하는 블루레이 크기의 최솟값이다' 라는 논리가 확실히 납득되지 않는다.
어느 상황에서도 정말 시작인덱스가 블루레이 크기의 최솟값이 되는걸까?
-> start와 end가 있을 때, end+1이상의 값들은 정답으로 보장되는 값이다.
따라서 start와 end가 뒤바뀐 후 while문을 빠져나오면 end+1로 있는 start의 값이 최소값으로 보장되는것이다!!
참고
Do it 알고리즘 코딩테스트 자바편
