[백준 2343] 기타 레슨 (JAVA)

백준 2343번 문제  - 기타 레슨

2343번: 기타 레슨

---

문제 분석

 

• 주어진 순서대로 녹음되어야한다. 
• 해당 순서를 따랐을때, 이들을 M개로 나눠서 녹음할 때 가장 최소 강의 길이를 출력해라 (강의 길이는 M개 모두 같아야한다)

---

 

해결 키 포인트

 

• 값을 입력 받을 때
  
  • 입력 값들의 최대 값을 start(최소 블루레이 시간)
  • 입력 값들의 합을 end(최대 블루레이 시간)
• start가 end보다 커질 때까지 반복하면서 블루레이 시간을 알아낸다
  • start와 end의 중앙 값을 알아내 이를 블루레이 시간으로 정했을 때, 해당 값이 합보다 커지기 전에 count 증가
• 이렇게 구해진 count가 필요한 블루레이 개수

 

---

이진 탐색

 

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙 값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

알고리즘

 

1. 현재 데이터셋의 중앙값을 선택
2. 중앙값 > 타깃 데이터 일 때 : 중앙 값 기준으로 왼쪽 데이터 셋 선택
   중앙값 < 타깃 데이터 일 때 : 중앙 값 기준으로 오른쪽 데이터 셋 선택
3. 과정 1~2를 반복하다, 중앙값 == 타깃 데이터 일 때 : 탐색 종료

Do It! 알고리즘 코딩 테스트

 

---

코드

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

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

        // N, M 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int start = 0;
        int end = 0;

        // N개의 A 입력
        int A[] = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());

            // 현재 입력 값들의 최대 값을 start로, 전체 합을 end로
            start = Math.max(start, A[i]);
            end += A[i];
        }

        // M개의 블루레이로 나눌때 최소 블루레이 값을 아아내기 위한 반복문

        // 블루레이 가능 시작 값(최소)이 끝 값(최대)보다 커질 때 까지
        while (start <= end) {
            // 중앙 값 알아내기
            int mid = start + (end-start) / 2;
            int sum = 0;
            int count = 0;
            // 전체 배열을 확인하면서 배열 합이 중앙값보다 크면 count 증가 및 초기화
            for(int i=0;i<N;i++) {
                if(sum + A[i] > mid) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            // sum이 0이 아니면 count 추가
            if(sum != 0)
                count++;

            // count가 M보다 크면, M개의 블루레이로 불가능 한 것이므로 최소 값 증가
            if(count > M)
                start = mid + 1;
            // count가 M보다 작으면, M개의 블루레이로 가능 한 것이므로 최대 값 증가
            else
                end = mid -1;
        }
        System.out.println(start);
    }
}