생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 2343번 기타 레슨

생각중임 2024. 2. 14. 00:44

기타 레슨

문제 설명

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

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

출력

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

제한사항

  • 없음

입출력 예

input return
9 3
1 2 3 4 5 6 7 8 9		 17

문제 분석

강의를 배열에 넣어주고 가장 큰 강의 길이와 강의의 총길이를 구한다. 
강의를 넣은 배열을 오름차순 정렬해준다. x -> 문제의 조건에 정렬을 하면 안 된다.
가장 큰 강의와 강의의 총길이 사이에서 이분 탐색을 한다.
이분 탐색을 하면서 중간값을 기준으로 강의를 블루레이에 나눠 담는다.

블루레이의 개수와 비교해 블루레이의 크기를 조절해 최소 크기를 구할 수 있다.

손으로 풀기

  1. 입력값을 반복하면서 배열에 넣어주면서 강의의 총길이와 가장 긴 강의를 구한다.
  2. 가장 긴 강의부터 총 강의 길이 사이를 이분 탐색을 해준다.
  3. 이분 탐색 도중 해당 강의 시간의 기준으로 블루레이를 나눠 계산을 하면서 블루레이의 개수를 구한다.
  4. 블루레이의 개수가 주어진 개수보다 많으면 left를 키워 블루레이의 크기를 키워 개수를 줄인다.
  5. 블루레이의 개수가 주어진 개수와 같거나 적으면 right를 줄여 블루레이의 크기를 줄여 개수를 늘린다.

나의 문제풀이

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

public class Main {
    
    static int[] lecture;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        int sum = 0;
        int max = 0;
        lecture = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // 입력값을 받으면서 가장 긴 강의 길이와 강의의 총길이를 구한다.
        for (int i = 0; i < N; i++) {
            lecture[i] = Integer.parseInt(stringTokenizer.nextToken());
            sum += lecture[i];
            max = Math.max(max, lecture[i]);
        }
        bufferedReader.close();

        System.out.println(binarySearch(max, sum, M));
    }

    public static int binarySearch(int left, int right, int target) {

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 블루레이에 강의 나누기
            int total = 0;
            int cnt = 1;
            // 앞부분 부터 잘라서 기준이 되는 블루레이 크기 비교해 넘어가면 다음 블루레이로 초기화해 계산
            for (int i = 0; i < N; i++) {
                if (total + lecture[i] > mid) {
                    cnt++;
                    total = 0;
                }
                total += lecture[i];
            }

            if (cnt > target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

이분 탐색의 기준이 주어지는 값으로 만든 배열이 아닌, 가상의 크기를 구간으로 사용해서 사용하는 점과 이분 탐색 도중 별도의 블루레이 크기를 구하는 게 문제의 핵심이었다. 그래도 생각보다는 간단한 느낌이었는데, 계속 오류가 생겨 도무지 구현에 무슨 문제 있는지를 못 찾고 있어 질문 게시판을 보다 보니 알 수 있었다.
문제는 문제를 제대로 읽어두지 않았다는 점.. 이분 탐색을 위해서 대부분의 문제에서 주어진 배열을 정렬된 상태에서 이분 탐색을 하기 때문에 주어진 배열을 자연스럽게 정렬을 했는데, 애초에 배열자체가 이분 탐색의 기준이 되는 것도 아니었는데 정렬을 한 점과 문제 자체에서 정렬을 하지 말라고 해둔 부분이 있었는데, 문제를 풀면서 그 부분을 고려를 안 하고 문제를 풀고 있으니 계속 오류가 났다. 문제에서 제한사항을 제시를 해줄 수 도 있지만, 문제 설명을 통해서 제한사항을 말해줄 수 도 있는 점을 꼭 다시 유의하고 머릿속에 새겨야겠다.

알고리즘 분류

  • 이분 탐색
  • 매개 변수 탐색

문제 출처 - https://www.acmicpc.net/problem/2343

 

2343번: 기타 레슨

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경

www.acmicpc.net