[BOJ 2343] 기타 레슨

[BOJ 2343] 기타 레슨

 

1. 문제 : https://www.acmicpc.net/problem/2343

 

2. 풀이

기존 영상 합+ 새로운 영상 > 비디오 길이 -> +1

기존 영상 합을 0으로 만들고 다시 반복문

sum += arr[i] 하면 0으로 만든 후에도 값 더해주는 것 가능 (인덱스 변경 불필요)

반복문 다 돌고 sum이 0이 아니면 남은 비디오가 남아있다는 소리기 때문에 +1

 

upper bound, lower bound 업데이트 해주며 반복

3. 코드

package baekjoon;

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

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

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

        while (left <= right) {
            int mid = (left + right) / 2;
            int sum = 0;
            int k = 0;
            for (int i = 0; i < n; i++) {
                if (sum + arr[i] > mid) {
                    sum = 0;
                    k++;
                }
                sum += arr[i];
            }

            if (sum != 0) k++;

            if (k > m) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(left);
    }
}