백준 1166 선물 Java

: ) YOUNG·2023년 5월 7일
1

알고리즘

목록 보기
190/417
post-thumbnail

백준 1166번
https://www.acmicpc.net/problem/1166

문제




생각하기


  • 이분탐색 문제이다.
    • 반복문과 재귀 2가지로 구현했다.

동작



재귀

반복문


코드


Java

재귀


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

public class Main {
    private static int N, L, W, H;
    private static double result = 0;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        sb.append(binarySearch(0.0, Math.max(L, Math.max(W, H)), 0));
        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static double binarySearch(double low, double high, int count) {
        if (low > high || count == 60) {
            return low;
        }

        double mid = (low + high) / 2.0;

        if (check(mid)) {
            low = mid;
            double temp = binarySearch(low, high, count + 1);

            if (temp == -1) {
                return low;
            } else {
                return temp;
            }
        } else {
            high = mid;
            return binarySearch(low, high, count + 1);
        }
    } // End of binarySearch

    private static boolean check(double mid) {
        if ((long) (L / mid) * (long) (W / mid) * (long) (H / mid) >= N) {
            // check가 true이면, low = mid가 됨 (기준 높임).
            return true;
        } else {
            // check가 false이면, high = mid가 된다 (기준 내림).
            return false;
        }

    } // End of check
} // End of Main class

반복문


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

public class Main {
    private static int N, L, W, H;
    private static double result = 0;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        sb.append(binarySearch(0.0, Math.max(L, Math.max(W, H))));

        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static double binarySearch(double low, double high) {
        for (int i = 0; i < 10000; i++) {
            double mid = (low + high) / 2.0;

            if ((long) (L / mid) * (long) (W / mid) * (long) (H / mid) >= N) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return low;
    } // End of binarySearch
} // End of Main class

0개의 댓글