백준 1088 케이크 자바

ChoRong0824·2023년 6월 2일
1

백준

목록 보기
3/14
post-thumbnail

저의 100번째 포스팅을 자축하기 위해, 어떤 문제를 풀지 고민하다,
케이크는 주로 기념일에 먹으며, 상징성은 기념일이라 생각합니다.
따라서, 백준의 문제로 있어 100번째 기념으로
플레티넘2, 케이크 문제를 풀게 되었습니다.. ㅋㅋㅋ
To celebrate my 100th posting on Velog, I will tackle a Platinum 2 level cake problem of the Baekjoon website.
영어를 못하지만 백 번째 기념으로 영어도 한 번 써봤습니다.

문제

출처 : https://www.acmicpc.net/problem/1088




접근방법

(필자 생각입니다)

1.

최소 무ㄱ 차이를 계산하려면, 각 케이크 조각과 자르는 횟수를 고려해야함. --> 각 조각을 자를때마다 그 조각의 무게는 절반 (문제에 나와있음.)
--> 입력 받은 무게를 내림차순으로 정렬하고, 케이크 자르기 작업에 우선순위 큐를 사용

2.

모든 케익 조각에 대한 우선순위 큐를 사용하여 각 케이크 조각의 두 가지 정보를 저장해줌 -->
이 방식은 보통 (우선순위큐)?로 처리할 수 있고, 다른방법은 필자가 잘 모릅니다ㅜ...
혹여, 우선순위 큐를 모른다면 구글링해서 우선순위 큐에 대해 학습하시는 것을 권장드립니다. -->
무게와 해당 조각을 자른 횟수를 저장 한 후, 우선순위 큐는 무게와 자른 횟수의 비율에 따라 정렬시킴.
참고로 여기서 키 포인트는 처음에는 모든 케이크 조각에 대해 해당 배열의 값이 0이다 라는 것입니다.

3.

M번 (최대) 잘라야함 --> 즉, 반복해야함.
a. 가장 높은 무게 비율을 가진 케이크를 선택(우선순위 큐에서 추출).
b. 선택된 케이크 조각을 반으로 나눈다(무게를 두 배로 나눔).
c. 나누어진 케이크 조각의 새로운 무게 비율을 계산고 우선순위 큐에 다시 추가해줌

쉽게 설명해서,
최대 M 번 자르기 위해 다음 단계를 반복할 예정입니다.
a. 가장 무거운 케이크 조각의덱스를 찾는다.
b. 해당 인덱스의 절단 횟수를 1 증가시킨다.
c. 같은 인덱스의 케크 조각 무게를 업데이트한다. 무게는 원래 무게를 (절단 횟수+1)로 나눌 것이다.
d. 다시 무게 배열을 내림차순으로 정렬

4.

M 번의 케이크 자르기 작업이 끝났다면, 우선순위 큐를 비울 때까지 가장 무거운 조각과 가장 가벼운 조각의 무게 차이를 구하여 최소 무게 차이를 찾아줘야함.

마지막

당연스레, 최소 무게 출력.


Code

1차시도

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        PriorityQueue<Double> cakePieces = new PriorityQueue<>(); //우선순위 큐, 자동으로 작은 값 순으로 정렬
        for (int i = 0; i < N; i++) {
            cakePieces.add(Double.parseDouble(st.nextToken())); // 큐 추가, 파싱 후, 실수형으로 저장
        }

        int M = Integer.parseInt(br.readLine()); // 최대 케이크를 자를 수 잇는 횟수

        while (M > 0) { // m만큼 자르는 과정 반복
            double max = cakePieces.poll(); // POLL은 가장 작은 원소를 가져오고 그 원소를 삭제함.

            double newFirst = max / 2.0;
            double newSecond = max - newFirst;
            cakePieces.add(newFirst);
            cakePieces.add(newSecond);
            /*
            윗 코드 부분을 좀더 이해하기 쉽게 설명하자면,
            max 케이크 조각을 반으로 나눈 값을 newFirst와 newSecond에 저장한 후
            이 값들을 나중에 두 개의 새로운 조각으로 추가하는거임.
            즉, 새로운 케이크 조각들인 newFirst와 newSecond를
            다시 cakePieces 큐에 추가한다는 느낌을 인지하면 되는거임.\
            (여기서 키포인트) 이때 PriorityQueue가 자동으로 정렬해줌.
            */
            
            M--; // M회만큼 반복 돌리는거임 (쉽게 설명하면, M값을 줄여가면서 과정 반복임)
        }

        double weightDifference = cakePieces.poll() - cakePieces.peek(); // 최종적 최대 무게
        /*
         cakePieces.poll()은 PriorityQueue에서 가장 큰 값을 가져오고 그 원소를 삭제함.
         (가장 큰 원소 가져온 후 삭제) --> 걍 함수 활용임. 외우면됨.
         poll()을 두 번 사용하면 두 번째로 큰 원소를 가져오게 됨. 
         (첫 번째 poll()에서 가장 큰 값을 가져오고 삭제했으므로, 남은 조각 중 가장 큰 값을 가져온다는 말입니다)
         
        cakePieces.peek()을 사용하여 이제 남은 PriorityQueue에서 가장 큰 원소를 가져옴.
        BUT원소를 삭제하지는 않음. --> 즉, peek 함수는 pill가 다르게 원소가 살아있음.
        이 코드는 무게 차이를 계산하기 위해 두 번째로 큰 원소를 가져올 때 사용할 예정.
        
        */

        bw.write(String.valueOf(weightDifference)); //  가장 큰 두 개의 케이크 조각의 무게 차이
        bw.flush();
        bw.close();
        br.close();
    }
}

2차시도 (이분탐색 검색)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weights = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        double result = findMinWeightDifference(N, weights, M);
        bw.write(Double.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    static double findMinWeightDifference(int N, int[] weights, int M) {
        double left = 0;
        double right = 1_000_000_000;
        for (int i = 0; i < 100; i++) {
            double mid = (left + right) / 2;
            int cuts = calculateCuts(weights, mid);
            if (cuts >= M) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    static int calculateCuts(int[] weights, double target) {
        int cuts = 0;
        for (int weight : weights) {
            cuts += (int) (weight / target);
        }
        return cuts;
    }
}

방법 3 그리디 알고리즘

public class Main {
    static class CakePiece implements Comparable<CakePiece> {
        int weight;
        int cuts;

        public CakePiece(int weight, int cuts) {
            this.weight = weight;
            this.cuts = cuts;
        }

        @Override
        public int compareTo(CakePiece o) {
            return Double.compare((double) o.weight / (o.cuts + 1), (double) weight / (cuts + 1));
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] weights = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());

        double result = minimalDifference(N, weights, M);
        System.out.println(result);
    }

    public static double minimalDifference(int N, int[] weights, int M) {
        PriorityQueue<CakePiece> pieces = new PriorityQueue<>();
        Arrays.stream(weights).forEach(weight -> pieces.offer(new CakePiece(weight, 0)));

        while (M-- > 0) {
            CakePiece piece = pieces.poll();
            piece.cuts++;
            pieces.offer(piece);
        }

        double max = Double.MIN_VALUE;
        double min = Double.MAX_VALUE;

        while (!pieces.isEmpty()) {
            CakePiece piece = pieces.poll();
            double avg = (double) piece.weight / (piece.cuts + 1);
            max = Math.max(avg, max);
            min = Math.min(avg, min);
        }

        return max - min;
    }
}

4트, 이진 탐색

public class Main {
    public static boolean check(List<Integer> weights, int m, double mid) {
        int cuts = 0;
        for (int weight : weights) {
            cuts += (weight % mid == 0) ? 0 : (weight % mid);
        }
        cuts /= m;

        int total = 0;
        for (int weight : weights) {
            total += weight / mid;
        }

        return total >= (cuts + weights.size());
    }

    public static double getMinimum(List<Integer> weights, int m) {
        double left = 0;
        double right = 0;
        for (int weight : weights) {
            if (weight > right) {
                right = weight;
            }
        }
        double result = Double.POSITIVE_INFINITY;

        for (int i = 0; i < 100; i++) {
            double mid = (left + right) / 2;
            if (check(weights, m, mid)) {
                left = mid;
                result = Math.min(result, right - mid);
            } else {
                right = mid;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        List<Integer> weights = new ArrayList<>();
        for (String weight : input) {
            weights.add(Integer.parseInt(weight));
        }
        int m = Integer.parseInt(br.readLine());
        System.out.println(getMinimum(weights, m));
    }
}

허허..허허허허..허허허허허..허허허...ㅎ

5트, 이진 탐색2

import java.io.*;
import java.util.*;

public class Main {

    public static boolean check(int[] weights, int m, double target) {
        int pieces = 0;
        for (int weight : weights) {
            pieces += (int) (weight / target);
        }
        
        return pieces >= m;
    }

    public static double getMinimum(int[] weights, int m) {
        double left = 1;
        double right = Arrays.stream(weights).max().getAsInt(); // 가장 큰 무게값
        double result = right;

        while (right - left > 1e-6) { // 소수점 정확도가 1e-6이 될 때까지 진행합니다.
            double mid = (right + left) / 2;
            if (check(weights, m, mid)) {
                left = mid;
                result = mid;
            } else {
                right = mid;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = Integer.parseInt(input[i]);
        }
        int m = Integer.parseInt(br.readLine());
        System.out.printf("%.6f%n", getMinimum(weights, m));
    }
}

6트,

(참고) 해서, 자바코드로 수정 및 필자 방식으로 코드 구성

import java.util.*;
import java.io.*;

public class Main {
    static class PieceInfo implements Comparable<PieceInfo> {
        double value;
        int index, count;

        public PieceInfo(double value, int index, int count) {
            this.value = value;
            this.index = index;
            this.count = count;
        }

        @Override
        public int compareTo(PieceInfo other) {
            return Double.compare(other.value, this.value);
        }
    }

    public static double solve(List<Double> heights, int cuts) {
        int size = heights.size();
        PriorityQueue<PieceInfo> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < size; i++) {
            priorityQueue.offer(new PieceInfo(heights.get(i), i, 1));
        }

        double minHeight = Collections.min(heights);
        double result = priorityQueue.peek().value - minHeight;

        for (int i = 0; i < cuts; i++) {
            PieceInfo pieceInfo = priorityQueue.poll();
            minHeight = Math.min(minHeight, pieceInfo.value / (pieceInfo.count + 1));
            priorityQueue.offer(new PieceInfo(pieceInfo.value * pieceInfo.count / (pieceInfo.count + 1), pieceInfo.index, pieceInfo.count + 1));
            result = Math.min(result, priorityQueue.peek().value - minHeight);
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(reader.readLine());
        List<Double> heights = new ArrayList<>();

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < size; i++) {
            heights.add(Double.parseDouble(tokenizer.nextToken()));
        }

        int cuts = Integer.parseInt(reader.readLine());

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        writer.write(String.format("%.12f", solve(heights, cuts)));
        writer.newLine();
        writer.flush();
    }
}

7트,

import java.util.*;
import java.io.*;

public class Main {
    static class CakePiece {
        double size;
        int numPieces;

        public CakePiece(double size, int numPieces) {
            this.size = size;
            this.numPieces = numPieces;
        }
        double pieceSize() {
            return size / numPieces;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(reader.readLine());
        List<Double> heights = new ArrayList<>();

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < size; i++) {
            heights.add(Double.parseDouble(tokenizer.nextToken()));
        }

        int cuts = Integer.parseInt(reader.readLine());

        PriorityQueue<CakePiece> priorityQueue = new PriorityQueue<>(Comparator.comparingDouble(CakePiece::pieceSize).reversed());
        for (double height : heights) {
            priorityQueue.offer(new CakePiece(height, 1));
        }

        for (int i = 0; i < cuts; i++) {
            CakePiece largestPiece = priorityQueue.poll();
            largestPiece.numPieces++;
            priorityQueue.offer(largestPiece);
        }

        double minHeight = priorityQueue.poll().pieceSize();

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        writer.write(String.format("%.12f", minHeight));
        writer.newLine();
        writer.flush();
    }
}

8트, 이분탐색...

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
        // 케이크 개수와 자르는 횟수 입력
        String line = br.readLine();
        if (line == null || line.trim().isEmpty()) {
            return;
        }

        StringTokenizer st = new StringTokenizer(line);
        if(!st.hasMoreTokens()) 
            return; // 
        int n = Integer.parseInt(st.nextToken());
        if(!st.hasMoreTokens()) 
            return; //
        int k = Integer.parseInt(st.nextToken());

        // 각 케이크의 높이 입력
        line = br.readLine();
        if (line == null || line.trim().isEmpty()) {
            return;
        }

        double[] heights = new double[n];
        st = new StringTokenizer(line);
        for (int i = 0; i < n; i++) {
            if(!st.hasMoreTokens())
                break; // 
            heights[i] = Double.parseDouble(st.nextToken());
        }

        // 이분 탐색을 위한 최소, 최대 높이 설정
        double left = 0.000_000_001;
        double right = 1_000_000_000;
        double mid;

        while (right - left >= 0.000_000_001) {
             mid = (left + right) / 2;

            int countCakes = 0;
            for (int i = 0; i < n; i++) {
                countCakes += (int) (heights[i] / mid);
            }

            if (countCakes >= k) {
                left = mid;
            } else {
                right = mid;
            }
        }

        // 결과 출력
        wr.write(String.format("%.12f", left));
        wr.newLine();
        wr.flush();
    }
}


(지운건 씨플플입니다) --> 제 코드로 맞춘 것이 아니라서, 손수 모자이크 처리했습니다.
분명 코드상으론 문제가 없다고,씨플플 코드로 이해를 하고, 자바로 잘 접근하고 있다고 필자는 생각했습니다.
필자는 백준을 풀 때, idea를 사용하지 않고, 백준 홈페이지에서 제출버튼을 눌러 바로 코드를 작성하던 습관을 들여놨습니다.
그래서 컴파일 오류도 정말 정말 많이뜨고, 분명 로직이 맞는데, 틀리는게 이상하다고 생각했습니다.
이에 인텔리제이에서 돌려보니, 출력값은 근사값으로 출력되는데, 정확하게 처리하는 로직은 어떻게 짜야하는 것일까요.... 해당 문제를 통해 아직 배워야할 것이 많다고 생각되네요..
하지만, 필자는 이해가 안됩니다.
이미 출력 전제조건이 : 첫째 줄에 가장 무게가 많이 나가는 조각과 적게 나가는 조각의 최소 무게 차이를 출력한다. 절대/상대 오차는 10^-9까지 허용한다. 라고 되어있는데, 그러면 아래와 같이 코드 구현을 해도 맞는 것이 아닌가요,,? ㅠㅠ 백준 너무 어렵네요..

9, 필자가 생각한 자바 정답코드

import java.util.*;
import java.io.*;

public class Main {
    static class Info implements Comparable<Info> {
        double val;
        int idx, cnt;

        public Info(double val, int idx, int cnt) {
            this.val = val;
            this.idx = idx;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Info i) {
            return i.val < this.val ? -1 : 1;
        }
    }

    static double sol(ArrayList<Double> v, int m) {
        int n = v.size();
        PriorityQueue<Info> PQ = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            PQ.offer(new Info(v.get(i), i, 1));
        }
        double mn = Collections.min(v);
        double ret = PQ.peek().val - mn;
        for (int i = 0; i < m; i++) {
            Info info = PQ.poll();
            double val = info.val;
            int idx = info.idx;
            int cnt = info.cnt;
            val = v.get(idx) / (double) (++cnt);
            PQ.offer(new Info(val, idx, cnt));
            mn = Math.min(mn, val);
            ret = Math.min(ret, PQ.peek().val - mn);
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Double> v = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            v.add(Double.parseDouble(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        System.out.printf("%.12f", sol(v, m));
    }
}

입력 예시에 원하는 값을 출력하려고
메인 함수 부분을 수정한다면 ? 즉, 자릿수를 표현해준다면 ?

 for (int i = 0; i < n; i++) {
            v.add(Double.parseDouble(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        double result = sol(v, m);
        result = Math.round(result * 1e12) / 1e12;
        System.out.println(result);
    }

자릿수 표현하는 방식 어렵네요... 안되네요 ㅜㅜㅜㅜㅜ

만약, 출력 형식을 .15f 로 변경하고, 소수 15자리에서 반올림 처리한다면 ?
--> 당연히, 예제 4번만 정상 값이 출력됩니다.. ☹️


계속 도전중입니다,, ㅠ

  • 수정

정답코드

DecimalFormat 클래스를 사용

자바에서 소수점 표현에 대해 공부를 해 본 결과,

코드에서 결과를 출력하기 전에 소수점 자리수를 조정하여 출력할 수 있습니다. DecimalFormat 클래스를 사용하여 결과값을 포맷할 수 있습니다.

import java.util.*;
import java.io.*;
import java.text.DecimalFormat;

public class Main {
    static class Info implements Comparable<Info> {
        double val;
        int idx, cnt;

        public Info(double val, int idx, int cnt) {
            this.val = val;
            this.idx = idx;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Info i) {
            return i.val < this.val ? -1 : 1;
        }
    }

    static double sol(ArrayList<Double> v, int m) {
        int n = v.size();
        PriorityQueue<Info> PQ = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            PQ.offer(new Info(v.get(i), i, 1));
        }
        double mn = Collections.min(v);
        double ret = PQ.peek().val - mn;
        for (int i = 0; i < m; i++) {
            Info info = PQ.poll();
            double val = info.val;
            int idx = info.idx;
            int cnt = info.cnt;
            val = v.get(idx) / (double) (++cnt);
            PQ.offer(new Info(val, idx, cnt));
            mn = Math.min(mn, val);
            ret = Math.min(ret, PQ.peek().val - mn);
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Double> v = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            v.add(Double.parseDouble(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        double result = sol(v, m);

        // 원하는 소수점 자리 범위로 반올림하여 출력합니다.
        DecimalFormat df = new DecimalFormat("#.################");
        System.out.println(df.format(result));
    }
}
  • 이렇게 수정하게 되면, 다른 테스트 케이스들도 전부 정적으로 동작해서 처리가 됩니다..
    (이전에는, 근사값으로 출력되었지만, 정적으로 소수점 표현을 고정해두고 문제를 풀어야 정확한 문제의 출력 값이 도출됩니다.)

즉, 여기서 키 포인트는 소수점 자릿수의 정적 처리입니다.
필자는 여기서 "정적" 표현을 쓴 이유는, 자릿수 고정을 했기 때문입니다. DecimalFormat df = new DecimalFormat("#.################");

7명 럭키7 입니다. 자바로는 아직 7분만 푼 문제네요 !
하루 종일 문제 접근 및 코드를 12~13시간 정도 봤는데,
이렇게 해결하고 나니, 개운하네요. ( 100% 제가 푼 것은 아니고, 중간에 구글링 해봄)

profile
컴퓨터공학과에 재학중이며, 백엔드를 지향하고 있습니다. 많이 부족하지만 열심히 노력해서 실력을 갈고 닦겠습니다. 부족하고 틀린 부분이 있을 수도 있지만 이쁘게 봐주시면 감사하겠습니다. 틀린 부분은 댓글 남겨주시면 제가 따로 학습 및 자료를 찾아봐서 제 것으로 만들도록 하겠습니다. 귀중한 시간 방문해주셔서 감사합니다.

0개의 댓글