030 : 블루레이 만들기

 

 

 

 

 

 

 

개수(counter)와 용량(plate set)은 반비례 관계

 

용량 기준으로 binary search를 진행하되, 용량이 초과시에 직전까지 것을 하나의 plate로 담음

 

해당 pointer의 TP[i]는 들어가지 않고 reset 후 다음 Plate로 들어감

 

같은 논리로, 직전까지 처리되고 해당것은 다음에 반영되는 TP-OP 구조로, 맨 끝 TP[V-1]가 남아있다면 추가 plate 할당 필요

 

counter가 3개보다 크다면 용량을 늘릴 필요가 있다

 

s <= e 로 s나 e만 출력하면 됨

 

 

 

 

 

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int T = sc.nextInt();

        // D2F
        int[] TP = new int[V];
        int s = 0;
        int e = 0;
        for (int i = 0; i < V; i++) {
            e += TP[i];
            if (s < TP[i])
                s = TP[i];
        }

        // OP
        while (s <= e) {

            int m = (s + e) / 2;
            int plate = 0;
            int counter = 0;

            for (int i = 0; i < V; i++) {
                if (plate + TP[i] > m) {
                    counter++;
                    plate = 0;
                }
                plate += TP[i];
            }
            if (plate != 0)
                counter++;


            if (counter > T)
                s = m+1;
            else
                e = m-1;
        }

        // OEC
        System.out.println(s);
    }
}