[백준 2343] 기타 레슨

🫡 문제

백준 2343 - 기타 레슨

🫡 코드

import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); //레슨 수
		int M = sc.nextInt(); //블루레이 개수 - 최소 크기 구하기
		
		int[] L = new int[N];
		
		int start = 0; //시작 인덱스 = 가장긴 레슨
		int end = 0; //끝 인덱스 = 모든 레슨 시간의 합
		
		
		for(int i=0; i<N; i++) {
			L[i] = sc.nextInt();
			if(start<L[i]) {	//가장 긴 레슨 구하기
				start = L[i];
			}
			end += L[i];	//모든 레슨의 합
		}
				
		while(start<=end) {	//시작 인덱스 > 끝 인덱스 --> 탐색 종료
			int mid = (start+end)/2;
			int sum = 0;//하나의 블루레이에 담을 수 있는 레슨의 합
			int cnt = 1; //블루레이 최대 3개 -> cnt == 1 부터 시작 
			
			for(int i=0; i<N; i++) {				
				
				if(sum + L[i]>mid) { //
					cnt++;			//합이 블루레이 크기보다 크면 새로운 블루레이에 담아줌
					sum = L[i];		//새로운 블루레이에 그 다음 레슨 담아주기
				}else {
					sum += L[i];	//합이 블루레이 크기보다 작으면 같은 블루레이에 계속 해서 레슨 담기
				}
			}		

			if(cnt>M) {	//레슨이 담긴 블루레이 개수 > 고정 블루레이 개수(3개) 
				//시작 인덱스 = 중앙값 + 1
				start = mid + 1;
				
			}else { //레슨이 담긴 블루레이 개수 <= 고정 블루레이 개수(3개) 
				//끝 인덱스 = 중앙값 - 1
				end = mid - 1;
			}
		}
		
		System.out.println(start);	
	}

}

🫡 풀이

N개의 강의를 M개의 같은 크기 블루레이에 다 담을 수 있는 블루레이 최소 크기를 구하는 문제

이분탐색문제

• 시작인덱스 = 가장 긴 레슨 수
• 끝 인덱스 = 모든 레슨이 걸리는 시간의 합
• 중앙값 = (시작+끝)/2

count = 중앙값에 모든 레슨들을 블루레이 3개로 나눠 담을 수 있을때 까지 +1

While문 → 첫번째 if-else문

1. if-else 문으로 변경해준 후 블루레이의 합이 중앙값보다 큰 경우
   1. if문 조건 안에서 블루레이 합을 계산 → 블루레이 개수 증가 및 새로운 블루레이 초기화
2. 블루레이의 합이 중앙값보다 작은 경우
   1. 계속 해서 같은 블루레이에 연속된 레슨을 담을 수 있기 때문에 누적해서 더해줌

두번째 if-else문

1. 레슨이 담긴 블루레이 개수가 정해진 고정 블루레이 개수 M개보다 큰 경우
   1. 중앙값 크기를 키워서 범위 재탐색
2. 레슨이 담긴 블루레이 개수가 정해진 고정 블루레이 개수 M개보다 작거나 같은 경우
   1. 중앙값 크기를 줄여서 범위 재탐색

1차 시도 코드 (실패)

import java.util.Scanner;

public class Main {

	// 모든 강의를 M개의 동일한 크기를 가진 블루레이에 담을 때 블루레이 최소 크기
	//1. 시작인덱스 = 가장 긴 레슨 수
	//2. 끝 인덱스 = 모든 레슨이 걸리는 시간의 합
	//3. (시작+끝)/2 = 중앙값
	//4. 중앙값에 모든 레슨들을 블루레이 3개로 나눠 담을 수 있을때 까지 +1 . 
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); //레슨 수
		int M = sc.nextInt(); //블루레이 개수 - 최소 크기 구하기
		
		int[] L = new int[N];
		
		int start = 0; //시작 인덱스 = 가장긴 레슨
		int end = 0; //끝 인덱스 = 모든 레슨 시간의 합
		
		
		for(int i=0; i<N; i++) {
			L[i] = sc.nextInt();
			if(start<L[i]) {	//가장 긴 레슨 구하기
				start = L[i];
			}
			end += L[i];	//모든 레슨의 합
		}
				
		while(start<=end) {	//시작 인덱스 > 끝 인덱스 --> 탐색 종료
			int mid = (start+end)/2;
			int sum = 0;//하나의 블루레이에 담을 수 있는 레슨의 합
			int cnt = 0; //블루레이 최대 3개
			
			for(int i=0; i<N; i++) {				
				
				
				if(sum>mid) { 
					cnt++;
					sum = 0; //합이 블루레이보다 크면 합을 멈추고 다음 레슨 값부터 다시 더해주기 위해 0으로 초기화
				}				
				sum += L[i];
			
			}		
			
			if(cnt>M) {
				//1. 중앙값 크기의 블루레이에 모든 레슨을 담을 수 있으면 끝 인덱스 = 중앙값-1
				end = mid - 1;
				
			}else {
				//2. 중앙값 크기의 블루레이에 모든 레슨을 담을 수 없으면 시작 인덱스 = 중앙값+1
				start = mid + 1;
			}
		}
		
		System.out.println(start);
		
		/*
		 * for(int i=0; i<N; i++) { System.out.print(L[i] + " "); }
		 * System.out.println("start = " + start + ", end = " + end);
		 */
		
	}

}

1차 시도 코드 풀이
블루레이 개수 cnt 가 최소 1개는 나올 것이니 cnt = 0 → cnt = 1 변경
While문 안에 있는 if문 조건에서 먼저 계속해서 sum+=L[i] 계산을 해주니
중앙값보다 크기가 큰 경우 다음 레슨 부터 새로운 블루레이에 담아주려 해도
다음 레슨이 차례대로 들어가지 않아 연산이 제대로 수행되지 않았습니다.