항해 99클럽 코딩테스트 스터디 5기 2일차 TIL (자바 / 미들러)

 

<오늘의 학습 키워드>

- 이분탐색법

<오늘의 문제>

제목 : 백준 / 브론즈2 / 27160번 할리갈리

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

<풀이>

처음 틀린답

package BOJ.탐색.랜선자르기_1654.insub2004_250114;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int N = Integer.parseInt(strings[0]);
        long M = Long.parseLong(strings[1]);
        
        long max = 0;
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            long input = Long.parseLong(br.readLine());
            if (input > max) {
                max = input;
            }
            list.add(input);
        }

        long result = getResult(max, list, M);

        System.out.println(result);
    }

    private static long getResult(long max, List<Long> list, long M) {
        long result = 0;
        long start = 1;
        long end = max;
        while (start <= end) {
            long mid = (start + end)/2;
            long totalSum = 0;
            for (int i = 0; i < list.size(); i++) {
                totalSum += list.get(i) / mid;
            }
            if (totalSum == M) {
                result = mid;
                break;
            } else if (totalSum < M) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return result;
    }
}

정답 맞은 답

package BOJ.탐색.랜선자르기_1654.insub2004_250114;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int N = Integer.parseInt(strings[0]);
        long M = Long.parseLong(strings[1]);
        
        long max = 0;
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            long input = Long.parseLong(br.readLine());
            if (input > max) {
                max = input;
            }
            list.add(input);
        }

        long result = getResult(max, list, M);

        System.out.println(result);
    }

    private static long getResult(long max, List<Long> list, long M) {
        long result = 0;
        long start = 1;
        long end = max;
        while (start <= end) {
            long mid = (start + end)/2;
            long totalSum = 0;
            for (int i = 0; i < list.size(); i++) {
                totalSum += list.get(i) / mid;
            }
           if (totalSum < M) {
                end = mid - 1;
            } else {
               result = mid;
               start = mid + 1;
            }
        }
        return result;
    }
}

 

해설

 

<결론, 주의할점>