문제 탐색하기

입력 자료 정리

1. 입력값 n은 나무의 개수, m은 필요한 나무 높이 합의 최소 수이다
2. 이어서 n만큼 들어오는 입력값들은 각각 나무의 높이이다

해결방법 추론

1. m의 최대 값을 보면 이 문제는 이분탐색으로 해결해야함을 알 수 있다
2. 나무를 자르는 톱의 가장 이상적인 높이를 구하는 문제이며,
   최소인 1부터 나무 높이의 최대값까지를 범위로 하여 그중 m을 만족시킬 수 있는
   최적의 값을 찾으면 되는 문제다
3. 만약 이렇게 해서 잘랐을 떄의 합이 m보다 크거나 같다면 정답을 찾은것이지만
   더 최적의 높이를 찾기 위해 left의 범위를 늘리고
   작다면 정답의 조건을 만족시키지 못했으므로 right범위를 줄이면 해결될 것이다
4. 한가지 주의할점은 left와 right를 합했을 때의 값이 int형 범위를 벗어날 수 있으므로
   left, right, mid는 모두 long타입으로 지정해야한다.

시간복잡도 계산

1. 시간복잡도는 m의 범위 내에서 이분탐색하면서 n만큼 합산하기 때문에
   n x logm의 연산이 발생한다
2. 따라서 시간복잡도는 O(n x logm)이 되며, 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. 입력값은 n크기의 int형 타입의 배열에 보관한다
2. 이때, max라는 변수를 -1로 초기화한뒤, 입력 원소와 비교하여 최대값을 관리한다
3. left는 1로 초기화하고 right는 앞서 선언한 max로 초기화한다
4. 정답 출력을 위한 ans도 long 타입으로 선언하며 0으로 초기화한다

이분탐색 설계

1. 이분탐색에 있어서 필요한 long타입의 sum 변수를 0으로 초기화한다
2. sum에는 n만큼 순회하면서 현재 원소의 값에서 mid를 뺀값을 넣어준다
3. 이때 0보다 작거나 같다면 0을 넣어주고 아닌 경우는 그 뺀값을 그대로 넣어준다
4. sum과 m을 비교하여 더 크거나 같다면 left의 값을 갱신한다
   이때, 정답의 조건을 만족시키므로 ans와 비교하여 더 큰 값을 ans에 넣어준다
5. 작을 때면 right의 값만 갱신시킨다

출력값 설계

1. 이분탐색결과 완성된 ans를 출력하면 정답이 된다.

정답코드

(1회차 시도 성공!)

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


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 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int max = -1;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }

        long left = 1;
        long right = max;
        long ans = 0;
        while(left <= right){
            long mid = (left + right) / 2;
            long sum = 0;
            for (int i = 0; i < n; i++) {
                sum += (arr[i] - mid > 0 ? arr[i] - mid : 0);
            }

            if(sum >= m){
                left = mid + 1;
                ans = Math.max(ans, mid);
            }else{
                right = mid - 1;
            }

        }

        bw.write(ans+"");
        
        br.close();
        bw.close();
    }

}

문제 링크

2805번 - 나무 자르기