[백준] #2343. 기타 레슨 (실버 1)

https://www.acmicpc.net/problem/2343

 

1. 이진탐색 대상 → 출력값인 블루레이의 최소 크기

2. 블루레이 최소 크기를 구하려는데 그에 대한 기본 low와 high값은? (블루레이의 개수 상관없이!)

• low : 블루레이 하나에 제일 큰 값 하나가 들어있는데 그보다 더 큰 다른 블루레이 크기가 없을 경우
  → 입력받은 강의 길이들 중 제일 큰 값
• high :  블루레이 하나에 모든 강의가 다 들어있는 경우
  → 모든 강의 길이 더한 값

3. 블루레이 개수는 어떻게 고려?
    ㄴ mid값을 블루레이의 크기로 했을 때 블루레이 개수가 몇개 필요한지 계산해본 후 

• 사용해야하는 블루레이 개수보다 mid값을 사용해 계산해본 블루레이 개수가
  • 많으면 : 개수가 더 많이 필요한 것이기 때문에 블루레이 크기가 지금보다 더 커져야 함 → low = mid + 1
  • 적으면(같으면) : 개수가 덜 필요한 것이기 때문에 블루레이 크기를 지금보다 줄여야 함 → high = mid - 1
    (주어진 블루레이 크기로 모든 강의를 녹화할 수 있는 경우에는 현재 크기가 가능한 최소 블루레이 크기라고 간주
      → minSize = mid)
    

 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] size = new int[n];


		int sum = 0;
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			size[i] = Integer.parseInt(st.nextToken());
			sum += size[i];
		}

		int low = size[n-1];
		int high = sum;
		int minSize = 0;

		while (low <= high) {
			int mid = (low+high) / 2;
			// int num = sum % mid != 0? (sum/mid)+1 : sum/mid;
			int num = 1;
			int sizeSum = 0;
			for (int s : size) {
				if (sizeSum + s > mid) {
					num++;
					sizeSum = 0;
				}
				sizeSum += s;
			}


			if (num > m) {
				low = mid + 1;
			}  else {
				minSize = mid;
				high = mid - 1;
			}
		}
		System.out.println(minSize);

	}
}

 

위의 코드로 인텔리제이에서 예시 입력값을 입력하여 실행 시에는 성공했지만
백준에 제출 시 실패하였음!

▼ ▼ ▼ ▼ ▼

입력값이 오름차순으로 입력되는 것이 아니라 주어진 입력값들 간 순서가 바뀌면 안됨! (블루레이를 녹화할 때 강의의 순서가 바뀌면 안됨)

그에 따라 mid값에 따른 블루레이 개수를 구하는 부분의 코드를 수정하였음

 

+) 입력값이 오름차순이 아니므로 min 또한 입력의 가장 마지막값이 아닌 입력값들 중 가장 큰 값을 찾아 설정하였음

 

최종 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] size = new int[n];


		int min = 0;
		int sum = 0;
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			size[i] = Integer.parseInt(st.nextToken());
			min = Math.max(min, size[i]);
			sum += size[i];
		}

		int low = min;
		int high = sum;
		int minSize = 0;

		while (low <= high) {
			int mid = (low+high) / 2;
			int num = 1;
			int sizeSum = 0;
			for (int s : size) {
				if (sizeSum + s > mid) {
					num++;
					sizeSum = 0;
				}
				sizeSum += s;
			}


			if (num > m) {
				low = mid + 1;
			}  else {
				minSize = mid;
				high = mid - 1;
			}
		}
		System.out.println(minSize);

	}
}