[백준 2343번] 기타레슨

get get get get a guitar 🎶

 

 

이진탐색 문제이다.

사실 실제 코딩테스트를 칠 때 이런 문제가 나오면 이진 탐색을 떠올릴 수 있을지 모르겠다..

 

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

public class B2343 {
    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[] lessons = new int[n];

        int left = 0;
        int right = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lessons[i] = Integer.parseInt(st.nextToken());
            right += lessons[i];  //총 레슨 시간
            left = Math.max(left, lessons[i]);  //레슨 시간이 가장 긴 레슨
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = getCnt(n, lessons, mid);
            if (cnt > m) {  //구역 수가 m보다 클 때
                left = mid + 1;
            } else {        //구역 수가 m보다 작거나 같을 때
                right = mid - 1;
            }
        }
        System.out.println(left);
    }

    private static int getCnt(int n, int[] lessons, int mid) {
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (sum + lessons[i] > mid) {
                sum = 0;
                cnt++;
            }
            sum += lessons[i];
        }
        if (sum != 0) {
            cnt++;
        }
        return cnt;
    }
}

 

🐑  코드 설명

getCnt

• mid: 블루레이의 크기
• 레슨의 수만큼 for문을 돈다.
• sum에 lesson의 시간을 하나씩 더한다.
  • 만약 지금까지의 레슨 시간의 합(sum)과 다음에 더할 레슨 시간의 합이 블루레이의 크기(mid)보다 커진다면, sum = 0으로 하고 cnt를 하나 늘린다.