[Algo] 백준 14627 파닭파닭 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/14627

메모리 : 75620 KB

시간 : 656 ms

언어 : Java 11

 

코드

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

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 S = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[] pa = new int[S];
        int len = 0;
        long sum = 0;
        for (int i = 0; i < S; i++) {
            pa[i] = Integer.parseInt(br.readLine());
            len = Math.max(len, pa[i]);
            sum += pa[i];
        }
        int cnt = 0;
        long left = 1;
        long right = len;
        while (left <= right) {
            cnt = 0;
            long mid = (left + right) / 2;
            for (int i = 0; i < S; i++) {
                cnt += pa[i] / mid;
            }
            if (cnt >= C) { // 파를 더 길게
                left = mid + 1;
            } else { // 파를 더 짧게
                right = mid - 1;
            }
        }
        long ans = sum - (C * right);
        System.out.println(ans);

    }
}

 

풀이

이 문제와 유사하다. https://pingu0130.tistory.com/134

[Algo] 백준 1654 랜선 자르기 JAVA

파닭에 최대한 많은 파를 넣고, 남은 파는 라면에 넣어먹는다. 파의 가장 긴 길이를 찾기 위해서는 이분탐색으로 파의 길이를 찾아주면서 pa배열을 돌아 판매할 파닭의 개수만큼 생산할 수 있는지 확인해주면 된다.