문제
나의풀이
import java.util.*;
class Main {
public int Count(int[] arr, int capacity) {
int cnt = 1;
int sum = 0;
for(int x : arr) {
if(sum + x > capacity) {
cnt++;
sum = x;
}
else sum+=x;
}
return cnt;
}
public int solution(int n, int m,int[] arr) {
int answer = 0;
int lt = Arrays.stream(arr).max().getAsInt();
int rt = Arrays.stream(arr).sum();
while(lt<=rt) {
int mid = (lt+rt)/2;
//cd개수가 m보다 작다는것은 capacity가 넉넉함을 의미. mid보다 더 큰 capacity 탐색 x
if(Count(arr, mid) <= m) {
answer = mid;
rt = mid-1;
}
//cd개수가 m보다 크면 capacity가 부족함을 뜻함.
else lt= mid + 1;
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) arr[i] = kb.nextInt();
System.out.print(T.solution(n, m, arr));
}
}풀이방법
결정알고리즘은 가장 최선의 답을 찾기위해 계속 탐색을 하는 알고리즘을 뜻한다.
lt(최솟값)를 9로 잡은 이유는, arr의 최댓값인 9분짜리의 곡을 cd에 담기위해선 최소 capacity가 9는 되어야하므로.
rt(최댓값)를 45로 잡은 이유는, arr의 모든 원소를 더한값을 한개의 cd에 넣어야 할 경우가 있을수 있으므로.
Count함수는 cd한개의 최대용량(mid)에 몇곡까지 나눠서 넣을수있는지 return하고 그 값이 m보다 작거나 같으면 최대용량이 넉넉하다는 의미이다.
ex) 최대용량이 30이면 한 cd에 1~7까지 넣고 다음cd에 8,9를 넣어서 2개의 cd만으로 모두 곡을 담을수있다. 그렇다면 당연히 30보다 더 큰 capacity는 더 작은 갯수의 cd에 담을수있음을 의미하므로 더이상 탐색해 볼 필요가 없다.
반대로, 최대용량이 5인 cd로 곡을 집어넣는다면, 1,2 넣고 3 넣고 4 넣고 ... 해서 cd의 갯수가 m보다 커지므로 5이하의 값을 볼 필요가없어진다.
핵심키워드
결정알고리즘을 할 때 처음 최솟값과 최댓값을 정하는 부분을 잘 신경써야 할 것 같다.
그리고, 많이 문제를 풀어보면서 어떤 경우에 결정알고리즘을 써야 효율적일지 연구해봐야겠다.
