ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

https://www.acmicpc.net/problem/2805

 

2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ

์ฒซ์งธ ์ค„์— ๋‚˜๋ฌด์˜ ์ˆ˜ N๊ณผ ์ƒ๊ทผ์ด๊ฐ€ ์ง‘์œผ๋กœ ๊ฐ€์ ธ๊ฐ€๋ ค๊ณ  ํ•˜๋Š” ๋‚˜๋ฌด์˜ ๊ธธ์ด M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) ๋‘˜์งธ ์ค„์—๋Š” ๋‚˜๋ฌด์˜ ๋†’์ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‚˜๋ฌด์˜ ๋†’์ด์˜ ํ•ฉ์€ ํ•ญ์ƒ M๋ณด

www.acmicpc.net

 

 

์ด ๊ธ€์€ ์ด๋ถ„ํƒ์ƒ‰์„ ์ด๋ฏธ ์•Œ๊ณ ์žˆ๋Š” ์‚ฌ๋žŒ์„ ๋Œ€์ƒ์œผ๋กœ ์ž‘์„ฑํ•œ๋‹ค.

  • ์ด๋ถ„ํƒ์ƒ‰์„ ์ด์šฉํ•ด ์ตœ์ ์˜ ๊ฐ’์„ ์ฐพ์•„๋‚ธ๋‹ค.
  • ์ด๋ถ„ํƒ์ƒ‰ ๋ฌธ์ œ์—์„œ๋Š” ๊ตฌํ•ด์•ผํ•˜๋Š” ๊ฐ’์„ ์ฐพ๊ณ  ํ•ด๋‹น ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ํ’€์ดํ•œ๋‹ค. ๋ณดํ†ต ์ •๋‹ต์„ ์š”๊ตฌํ•˜๋Š” ๊ฐ’๊ณผ ์ผ์น˜ํ•œ๋‹ค.
  • ํ•ด๋‹น ๋ฌธ์ œ์—์„œ๋Š” K(์ ˆ๋‹จ๊ธฐ์— ์„ค์ •ํ•  ๋†’์ด์˜ ์ตœ๋Œ“๊ฐ’)์ด ๊ธฐ์ค€ ๊ฐ’์ด๋‹ค.
  • ๋”ฐ๋ผ์„œ ๋ณ€ํ™”ํ•˜๋Š” K๋ฅผ ๊ธฐ์ค€์œผ๋กœ totalSlicedHeight(์ž˜๋ ค์ง„ ๋‚˜๋ฌด ๊ธธ์ด์˜ ํ•ฉ)์ด M(๊ฐ€์ ธ๊ฐ€์•ผํ•  ๋‚˜๋ฌด ๊ธธ์ด)๋ณด๋‹ค ๋ถ€์กฑํ•  ๋•Œ๋Š” K๋ฅผ ๊ฐ์†Œ์‹œํ‚ค๊ณ 
  • totalSlicedHeight๊ฐ€ M๋ณด๋‹ค ํด ๋•Œ๋Š” K๋ฅผ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
  • K์— ๋Œ€ํ•œ ์ด๋ถ„ํƒ์ƒ‰์ด ์ข…๋ฃŒ๋˜๋ฉด ํƒ์ƒ‰๋œ K๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ด๋ถ„ํƒ์ƒ‰์ด ์ข…๋ฃŒ๋˜๋Š” ์กฐ๊ฑด์€ start > end ์ด๋‹ค.

์ฝ”๋“œ

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class ๋‚˜๋ฌด_์ž๋ฅด๊ธฐ_2805 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        List<Integer> woodList = new ArrayList<>();

        int maxHeight = 0;

        for (String wood : br.readLine().split(" ")) {
            int woodHeight = Integer.parseInt(wood);
            woodList.add(woodHeight);
            maxHeight = Math.max(maxHeight, woodHeight);
        }


        long start = 0;
        long end = maxHeight;

        while (start <= end) {
            long mid = (start + end) / 2;

            long totalSlicedHeight = 0;

            for (Integer woodHeight : woodList) {
                long slice = woodHeight - mid;
                if (slice > 0) {
                    totalSlicedHeight += slice;
                }
            }

            if (totalSlicedHeight < M) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(Long.toString(end));

        bw.close();
        br.close();
    }
}
๋ฐ˜์‘ํ˜•