[99클럽 코테 스터디] 4일차 TIL - 백준 2343번 기타 레슨

 

오늘의 문제는 백준 2343번 '기타레슨'이다.

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

 

 

4일차 문제도 역시 이분 탐색을 활용하는 문제다.

어제 문제보다는 훨씬 직관적이어서 생각보다 수월하게 풀 수 있었다

 

문제 해결 아이디어

1. 블루레이 크기를 결정하는 것이 핵심이다. 따라서 이분 탐색을 적용할 수 있을 것 같았다.
2. 블루레이 크기의 최솟값은 가장 긴 강의 길이, 최댓값은 모든 강의 길이의 합이 된다.
3. mid 값을 블루레이 크기로 설정하고, 해당 크기에서 블루레이 개수를 계산한다.
4. 블루레이 개수가 M 이하이면 더 작은 블루레이 크기도 가능할 수 있으므로 줄이고, 많다면 블루레이 크기를 늘린다.

 

코드 구현

package Boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj2343 {
    static int[] arr;
    static int max, sum, start, end, result = 0;

    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());
        arr = new int[N];

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

        start = max;
        end = sum;
        result = sum;

        while (start <= end) {
            int mid = (start + end) / 2;
            int count = 1;
            int currentSum = 0;

            for (int i = 0; i < N; i++) {
                if (currentSum + arr[i] > mid) {
                    count++;
                    currentSum = arr[i];
                } else {
                    currentSum += arr[i];
                }
            }

            if (count <= M) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        System.out.println(result);
    }
}

문제 해결 과정

1. 이분 탐색 범위 설정
   • start는 가장 긴 강의의 길이,
   • end는 모든 강의 길이의 합,
   • mid는 블루레이의 크기로, 이때 몇 개의 블루레이가 필요한지 계산한다.
   • 블루레이 크기는 최소 max(가장 긴 강의 길이), 최대 sum(모든 강의 길이의 합)에서 탐색한다.
2. 이분 탐색 진행
   • mid 값을 블루레이 크기로 설정하고, 해당 크기에서 몇 개의 블루레이가 필요한지 계산한다.
   • 블루레이 개수가 M 이하이면 블루레이 크기를 줄이고, 초과하면 크기를 늘린다.
3. 최적의 블루레이 크기 출력
   • while 문이 끝난 후 result에 최적의 블루레이 크기가 저장된다.

 

시간 복잡도 분석

• 이분 탐색: 블루레이 크기 범위가 max ~ sum이므로 O(log(sum))
• 배열 순회: 각 mid 값에서 N개의 강의를 확인해야 하므로 O(N)
• 총 시간 복잡도: O(N log(sum))
  • N이 최대 100,000이므로 충분히 효율적이다.

 

오늘의 회고

이번 문제는 매개 변수 탐색을 활용하는 문제였는데, 어제보다 훨씬 직관적이어서 구현하는 데 시간이 오래 걸리지 않았다.

이제는 문제를 보고 어떤 탐색 방법을 써야 할지 빠르게 판단하는 능력을 키우는 것이 중요할 것 같다.

그리고.. 사소한 실수를 줄여야 한다!

이제 다른 이분 탐색 문제를 더 풀어보면서 연습을 해봐야겠다.