힌트 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다.
17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화할 수 없다.
결정 알고리즘에 대해 학습할 수 있는 알고리즘 문제였다.
이분 검색을 이용한 이 결정 알고리즘은 이분 검색에서 사용하는 lt와 rt 사이에 답이 무조건 존재한다는 가정에서 사용해야 한다. 우선 코드를 먼저 확인하고 이에 대한 설명을 진행하겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Review{
public static int count(int[] arr, int capacity){
int cnt=1,sum=0;
for(int x:arr){
if(sum+x>capacity){
cnt++;
sum=x;
}
else sum+=x;
}
return cnt;
}
public static int solution(int len, int num, int[] arr){
int lt=Arrays.stream(arr).max().getAsInt();
int rt= Arrays.stream(arr).sum();
int answer=0;
while(lt<=rt){
int mid=(lt+rt)/2;
if(count(arr,mid)<=num){ //mid가 DVD의 용량
answer=mid;
rt=mid-1;
}
else lt=mid+1;
}
return answer;
}
public static void main(String[] args)throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] str=br.readLine().split(" ");
int len=Integer.parseInt(str[0]);
int num=Integer.parseInt(str[1]);
String[] arr=br.readLine().split(" ");
int[] list=new int[len];
int k=0;
for(String s:arr){
list[k++]=Integer.parseInt(s);
}
System.out.println(solution(len,num,list));
}
강의를 참고해서 필자가 푼 마지막 코드다.
우선 lt와 rt는 뮤직 비디오를 저장할 최소, 최대 용량이다.
먼저 위 사진에서 예시 1을 확인하며 분석해보자.
lt
제일 큰 단일 뮤직비디오 용량이 9다. 만약에 각 뮤직비디오마다 DVD를 가진다면 최소 9의 용량을 가져야만 각 DVD에 모든 뮤직비디오 저장이 가능할 것이다. 이유는 DVD는 모두 같은 크기라고 가정하고 진행했기 때문이다.
따라서 lt는 최소 DVD 용량인 뮤직비디오 중 제일 큰 값이 들어가야 한다.
rt
rt는 단순하게 모든 뮤직비디오를 담아서 한 DVD에 넣을 수 있으므로 모든 뮤직비디오의 합을 값으로 가지면 된다.
이분 검색은 언젠가 lt가 rt와 같아지거나 커지므로 그때까지 반복문을 진행하면 된다.
그러면 이제 검색 논리 처럼 lt와 rt를 더하고 2로 나누어서 진행한다. 이 결괏값 이름은 변수 mid라고 지칭한다.
mid도 마찬가지로 DVD의 용량이다. 그러면 count메소드를 만들어서 해당 메소드의 리턴 값과 우리가 num이라고 받은 DVD의 개수를 비교하면 된다.
이제 여기서 count 메소드에 대해 살펴보자.
count 메소드는 앞에서 언급한 것처럼 DVD의 개수를 살피는 것이다. 우리는 해당 메소드에 뮤직비디오 배열(arr)과 mid(DVD의 용량, capacity)을 인자로 넣을 것이다. 코드는 아래와 같다.
public static int count(int[] arr, int capacity){
int cnt=1,sum=0;
for(int x:arr){
if(sum+x>capacity){
cnt++;
sum=x;
}
else sum+=x;
}
return cnt;
}
최소 DVD가 한개니까 DVD 개수를 세는 변수 cnt는 1로 초기화한다.
이제 arr을 반복문을 통해서 cnt를 계산하면된다. 각 뮤직비디오의 크기를 더하는 sum 변수를 만든다.
sum 변수에 순서대로 뮤직비디오를 더하는데 만약 용량이 커진다면 멈추고 다음 뮤직비디오를 sum변수에 넣고 더하면 된다. 위 예시 1을 통해 이해할 수 있다.
예시
현재 capacity 값이 17이다. 그러면 반복문을 통해 알아보자.
1+2+3+4+5 까지 진행했다. 그러면 값이 17이다.
여기서 6을 더하면 용량을 초과하므로 cnt를 1 올리고 sum에 다음 값인 6을 넣는다.
그러면 다시 6+7을 진행하고 8이 들어오면 17보다 커지므로 cnt를 1을 올리고 sum에 다음 값인 8을 넣는다.
이제 마지막 9를 더하면 마무리 된다. 이렇게 해서
(1,2,3,4,5) (6,7) (8,9) 이렇게 나누어진다.
그러면 이제 cnt를 리턴해서 if문에서 num변수와 비교한다.
만약 입력받은 DVD개수보다 작거나 같으면 answer에 현재 DVD 용량인 mid 값을 할당한다.
이후 더 좋은 값을 찾기 위해 rt=mid-1을 진행한다.
만약 가정문을 만족하지 못하면, 이 말은 DVD 용량이 너무 작다는 것이다. 그래서 lt 값을 올려 mid(용량)를 크게 만들기 위해 lt=mid+1을 진행한다.
이런 논리를 가지고 반복문을 진행하다보면 answer에 적합한 값이 들어가고 답을 구할 수 있다.
이상입니다. 감사합니다.
댓글