2805_나무 자르기 (JAVA) (C++)

2805번: 나무 자르기

 

[C++]

#include <cstdio>
#include <algorithm> //sort
using namespace std;

int n, minlength;
int namu[1000001];

long long cal(int length){ //집에 가져가는 나무의 높이 계산
    long long result = 0;
    for(int i=0; i<n; i++){
        if(namu[i]>length)
            result += namu[i]-length;
    }
    return result;
}

int main(){
    scanf("%d %d", &n, &minlength);
    
    for(int i=0; i<n; i++){
        scanf("%d", &namu[i]);
    }
    sort(namu, namu+n); //오름차순 정렬
    
    int mid;
    int left = 0;
    int right = namu[n-1]; //입력받은 나무길이의 최대값
    int temp = 0;
    // 예)3 1\n 1 2 2 의 경우, left>right되어 while문이 끝난다.
    // 이때, 마지막 mid값이 정답이 되므로 temp에 저장한다.

    while(left<=right){
        mid = (left+right)/2;
        long long x = cal(mid);

        if(x > minlength){
            temp = mid; //left>right 되었을 때를 대비해 저장
            left = mid+1;
        }
        else if(x < minlength)
            right = mid-1;
        else{
            printf("%d", mid);
            return 0;
        }
    }

    printf("%d", temp);
    
    return 0;
}

이분탐색 문제! 왜냐면 자료에서 특정값을 찾아야하고, 그 값을 예측하며 찾아야되니까

 

0 ~ namu[]배열의 최대값 사이의 숫자 중에서 '절단할 나무의 높이'를 찾는 것을 이분탐색으로 구현했다.

이를 위해 범위의 최소값(left)는 0, 최대값(right)은 입력받은 나무길이의 최대값인 namu[n-1]로 설정한다.

 

** 집에 가져가는 절단된 나무의 높이를 계산하는 cal()함수의 리턴값은 long long형을 사용해야 한다.

(int형으로 제출하면 시작하자마자 틀렸습니다 뜸!!)

 

 

 

 

[JAVA]

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	static int N, M;
	static int[] namu;

	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		namu = new int[N];
		for(int i=0; i<N; i++){
			namu[i] = sc.nextInt();
			total += namu[i];
		}
		Arrays.sort(namu);

		//무엇을 찾을 것인가? 절단기에 설정하는 높이
		//범위 기준: 집에 가져갈 수 있는 나무의 길이
		int left = 1; //범위 최소
		int right = namu[N-1]; //범위 최대
		while(left<=right){
			int temp = 0;
			int mid = (left+right)/2; //찾으려는 값
			for(int i=0; i<N; i++){
				if(mid<namu[i])
					temp += (namu[i]-mid);
			}

			if(temp < M){ //M보다 작으면- 높이를 줄여야함
				right = mid-1;
			}
			else{
				left = mid+1;
			}
		}
		System.out.println(right);
    }

}

 

1. 무엇을 찾을 것인가? - 절단기에 설정할 나무의 높이

2. '절단기에 설정할 나무의 높이' 의 범위는?

    문제에서 1 ≤ M ≤ 2,000,000,000 이렇게 M의 범위를 주어졌으므로, '절단기에 설정할 나무의 높이' 최소 범위는 1

    최대 범위는 namu[]에서 가장 큰 값 (이거보다 더 큰값은 해당X. 문제에서 M의 최소값을 원했으니까)

3. 집에 가져갈 수 있는 나무의 길이 temp를 M을 기준으로 크고 작음을 판단한다.

    만약 temp가 M보다 작다면, '절단기에 설정할 나무의 높이'를 줄여야 한다.  : right = mid-1;

    M보다 크다면, '절단기에 설정할 나무의 높이'를 늘려야 한다.  : left = mid+1;

4. '절단기에 설정할 나무의 높이'의 최댓값을 구해야 하므로, right이 답이다.