코드
import java.util.*;
//뮤직비디오(결정알고리즘)
class 뮤직비디오_ {
private static int count(int[] arr, int mid) {
int sum = 0, count =1; // 기본 배치를 한 개 하고 시작
System.out.println("======="+mid+"=======");
for(int num : arr) {
sum+=num;
if(mid<sum) {
sum = num;
count++;
}
}
System.out.println("앨범 수 "+count);
return count;
}
public static void main(String[] args){
int answer=0;
int[] arr = new Random().ints(10, 1,10)
.sorted()
.toArray();
System.out.println(Arrays.toString(arr));
int lt = arr[arr.length-1]; //가장 큰 노래 길이가 최소 한 1곡은 다 들어감
int rt = Arrays.stream(arr).sum();//모든 노래 길이 합이 가장 큰 경우의 수
int size = 5; // 앨범 개수
while(lt<=rt) {
int mid = (lt+rt)/2;
if(count(arr, mid) <= size) {
answer = mid;
rt = mid-1;
}else {
lt = mid+1;
}
}
System.out.println("앨범 당 합 곡길이 :"+answer);
}
}결과
[3, 6, 6, 6, 6, 7, 7, 8, 9, 9]
=======38=======
앨범 수 2
=======23=======
앨범 수 4
=======15=======
앨범 수 6
=======19=======
앨범 수 4
=======17=======
앨범 수 5
=======16=======
앨범 수 6
앨범 당 합 곡길이 :17반드시 이분 검색을 이용한 알고리즘은 정렬이 필수
'자료구조&알고리즘 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비' 카테고리의 다른 글
| 이진수 구하기(재귀) (0) | 2023.02.08 |
|---|---|
| 재귀함수 (0) | 2023.02.05 |
| 마구간 정하기 (0) | 2022.12.17 |
| 장난꾸러기 (0) | 2022.12.09 |
| LRU(Least Recently Used) (0) | 2022.12.06 |