https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
check함수의 반복문 처음에 각 영상이 디스크크기를 초과할 경우가 있다는 것을 확인해주지 않아서 풀이시간이 꽤 걸렸다.
import java.util.*;
import java.io.*;
public class Main
{
public static int n;
public static int m;
public static int[] input;
public static boolean check(int num){
int sum=0;
int count=1;
for(int i=0;i<n;i++){
if(input[i]>num) return false;
if(sum+input[i]<=num){
sum+=input[i];
}else{
count++;
sum=input[i];
}
}
if(count<=m){
return true;
}else{
return false;
}
}
public static int search(){
int l = 0;
int r= 1_000_000_000;
int ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
r=mid-1;
ans = mid;
}else{
l=mid+1;
}
}
return ans;
}
public static void main(String[] args) throws IOException{
//입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
n = Integer.valueOf(temp[0]);
m = Integer.valueOf(temp[1]);
input = new int[n];
temp = br.readLine().split(" ");
for(int i=0;i<n;i++){
input[i] = Integer.valueOf(temp[i]);
}
int ans = search();
System.out.println(ans);
}
}
import java.util.Scanner;
class Main
{
public static boolean isPossible(int[] lengths, int videoLength, int videoCount) {
int currentLength = 0;
int currentCount = 1;
for (int len : lengths) {
if (len > videoLength) return false;
if (currentLength + len > videoLength) {
if (++currentCount > videoCount) return false;
currentLength = 0;
}
currentLength += len;
}
return true;
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] lengths = new int[N];
for (int i = 0; i < N; i++)
lengths[i] = sc.nextInt();
int l = 1, r = N * 10000, ans = -1;
while (l <= r) {
int m = (l + r) / 2;
if (isPossible(lengths, m, M)) {
ans = m;
r = m - 1;
}
else l = m + 1;
}
System.out.println(ans);
}
}
'Problem Solving > 이진 탐색' 카테고리의 다른 글
BOJ2143 두 배열의 합* (1) | 2024.02.28 |
---|---|
BOJ2792 보석상자 (0) | 2024.02.28 |
BOJ2512 예산 (0) | 2024.02.28 |
BOJ2110 공유기 설치 (매개변수 탐색) (1) | 2024.02.27 |
BOJ6236 용돈관리 (매개변수 탐색) (1) | 2024.02.27 |