2. 알고리즘사이트/1. 백준
기타 레슨 [백준2343][실버 1][이분탐색][Java]
isaacToast
2020. 3. 17. 23:59
반응형
[광고 누르면 오늘의 행운 상승!!]
https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가
www.acmicpc.net
이분탐색 문제
1. 임의의 블루레이 크기 mid를 정한다.
2. 이분탐색을 시작하여 mid보다 작은 갯수를 구한다.
3. 구한 갯수가 m보다 작다면 최대값을 감소시킨다.
4. 반대의 경우 최솟값을 감소시킨다.
package Study0316;
import java.util.*;
public class 기타레슨 {
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 left = 0;
int right = 0;
for(int i=0; i<n; i++) {
a[i] = sc.nextInt();
right += a[i];
left = left < a[i] ? a[i] : left;
}
while(left <= right) {
int mid = (left + right)/2;
int sum = 0;
int cnt = 0;
for(int i=0; i<n; i++) {
if(sum + a[i] > mid) {
sum = 0;
cnt++;
}
sum += a[i];
}
if(sum != 0) cnt++;
if(cnt <= m) right = mid-1;
else left = mid+1;
}
System.out.println(left);
}
}
반응형