[이진탐색][Java][BOJ] #2343. 기타 레슨

#이진탐색  #Silver1

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

🌷 문제 설명

✏️ 백준 연습문제: #2343. 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다. 강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

⌨️ 입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다

🖨️ 출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

입출력 예

입력	출력
9 3 1 2 3 4 5 6 7 8 9	17

 

💡 해결 포인트

1. 이진탐색 문제는 일단 "어떤 값을 찾을 것인가"에 집중할 것. 즉 target number를 찾아야 한다.
- 그걸 파악하는게 너무너무너무너무 오래 걸렸다.
- 이 문제에서는, "블루레이 크기" 가 내가 찾는 값

2. 그 다음 중요한게 "범위 설정"
- left는 가장 긴 강의 길이보다는 커야한다. 
- 모든 강의는 최소한 가장 긴 강의를 담아야하기 때문.. 처음에 0으로 했는데 웬만한 테케는 다 돌아서 진짜 미쳐버리는 줄 알았다. 

3. Arrays.stream(numbers).max().getAsInt();
- Thank you gpt

반례
5 3
10 10 10 10 100

 

🌷 내 코드

1. 이진탐색

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

public class BOJ_2343 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("example.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄 입력
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]); // 강의의 갯수
        int M = Integer.parseInt(firstLine[1]); // 블루레이의 갯수

        // N개 강의의 길이 입력(강의 순서대로, 분 단위(자연수)로 주어짐)
        int[] numbers = new int[N];
        String [] thirdLine = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(thirdLine[i]);
        }

        // M개 블루레이의 길이 입력
        int left = Arrays.stream(numbers).max().getAsInt(); // 블루레이에 들어있는 값 중 가장 긴 강의 길이
        int right = 1,000,000,000; // 가능한 최댓값(N의 최댓값 * M의 최댓값)
        int answer = 0;

        while (left <= right) {
            int mid = (left + right) / 2; // 블루레이의 길이
            int sum = 0; // 블루레이에 담긴 강의 길이 합
            int cnt = 1; // 블루레이 개수

            for (int i = 0; i < N; i++) { // 강의 길이만큼 반복
                if (sum + numbers[i] > mid) { // 블루레이에 담긴 강의 길이가 블루레이의 길이보다 크면
                    cnt++; // 블루레이 개수 증가
                    sum = 0; // 블루레이 초기화
                }
                sum += numbers[i]; // 블루레이에 담긴 강의 길이 추가
                // System.out.println("sum: " + sum + ", cnt: " + cnt + ", mid: " + mid + ", left: " + left + ", right: " + right + ", answer: " + answer);
            }

            if (cnt <= M) { // 블루레이 개수가 M개 이하이면
                answer = mid; // 결과값에 블루레이의 길이 저장
                right = mid - 1; // 블루레이의 길이를 줄임
            } else { // 블루레이 개수가 M개보다 크면
                left = mid + 1; 
            }
        }
        System.out.println(answer);
    }
}

 

 

🌷 코멘트

ㅎㅎ 오늘은 진짜 삽질 많이헀다.. 아

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com

qminlee723 - Overview