boj.kr/2343 기타 레슨 (silver1) 자바 풀이

1. lo를 0, hi를 기타 레슨 시간 목록 lectures의 총합으로 초기화한다.

2. 출력할 변수 ans에는 hi를 저장한다.

3. lo가 hi이하이면 아래 4-9를 반복한다.

4. mid에 (lo+hi)/2를 저장한다.

5. mid가 lectures 요소 중 최대값보다 작으면, lo를 mid+1으로 저장하고 다음 반복으로 넘어간다.

6. subLen을 0, subCnt를 1으로 초기화하고 lectures를 순회하면서 아래 6.1-6.2를 반복한다.

6.1. subLen에 lectures의 요소를 더한 값이 mid 이하이면 sub에 lectures의 요소를 더한다.

6.2. 만약 mid보다 크다면 subCnt에 1을 더하고 subLen에는 lectures의 요소를 저장한다.

7. subCnt가 M(블루레이의 개수) 이하이면 ans에 ans와 mid 중 더 작은 값을 저장한다.

8. hi를 mid-1으로 갱신한다.

9. subCnt가 M보다 크면 lo에 mid+1으로 갱신한다.

10. ans를 출력한다

 

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

public class Main {

    static int N;
    static int M;
    static int[] lectures;
    static int maxLen;
    static int subLen;
    static int subCnt;
    static int lo;
    static int hi;
    static int mid;
    static int ans;

    public static void main(String[] args) {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            lectures = new int[N];
            lo = 0;
            st = new StringTokenizer(br.readLine());
            for (int i=0; i<N; i++) {
                lectures[i] = Integer.parseInt(st.nextToken());
                maxLen = Math.max(maxLen, lectures[i]);
                hi += lectures[i];
            }
            ans = hi;
            while (lo <= hi) {
                mid = (lo+hi) / 2;
                if (mid < maxLen){
                    lo = mid + 1;
                    continue;
                }
                subLen = 0;
                subCnt = 1;
                for (int i=0; i<N; i++) {
                    if ((subLen + lectures[i]) <= mid) {
                        subLen += lectures[i];
                    } else {
                        subCnt += 1;
                        subLen = lectures[i];
                    }
                }
                if (subCnt <= M) {
                    ans = Math.min(ans, mid);
                    hi = mid-1;
                } else {
                    lo = mid+1;
                }
            }

            System.out.println(ans);
        } catch(Exception e) {
            e.printStackTrace();
        }

    }

}