백준 자바 2805 알고리즘 '나무 자르기 문제' 문제풀이

날씨가 많이 쌀쌀해졌군요

추운 날씨속에 학교 앞 자취방에서 코딩을 해봅니다.

코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 2805번 문제 링크

More info: 나무자르기 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘

첫번째 시도 (시간초과로 틀림)

Procedure findMaxH(long[] a, long p, long r, Long m)

Inputs :
- a : the array to search in
- p : the value we are searching for in a(min) m의 촤소값
- r : the value we are searching for in a(max) m의 최대값
- m : the value we are searching for in a(equal) 잘라야하는 나무의 값

Outputs :
- 잘라야하는 나무 산출량의 최대 높이

1. 최소값을 0, 최대값을 나무의 최대크기로 정한다.
2. 최소값 + 최대값의 평균값인 q를 구한다.
3. q 값일때 나무 산출량을 H를 ValueOfTreeOutput을 통해 구한다.
   a) H가 m 보다 크면 최소값을 q+1로 수정한다
   b) H가 m 보다 작으면 최대값을 q-1로 수정한다
   c) H와m이 같다면 q를 반환한다.
4. recursive 재귀적으로 돌린다.
   
   
   
   

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Long M = sc.nextLong();
        long a[] = new long[N];
        long maxLength = 0;


        for(int i = 0; i<N; i++){
            //Tree length
            a[i] = sc.nextLong();
            maxLength = Math.max(a[i],maxLength);
        }

        System.out.println(findMaxH(a, 0, maxLength, M));
    }


    private static long findMaxH(long[] a, long p, long r, Long m) {
        long q = (p+r)/2;

        long H = ValueOfTreeOutput(a, q);

        if (H > m){
            return findMaxH(a,q+1,r,m);
        }

        else if (H < m){
            return findMaxH(a,p,q-1,m);
        }

        else{
            return q;
        }
    }

    private static long ValueOfTreeOutput(long[] a, Long H) {

        long sum = 0;

        for(int i = 0; i<a.length; i++){

            long temp = a[i] - H;

            if(temp > 0){
                sum += temp;
            }
        }
        return sum;
    }
}

n번째 시도 (성공)

위에 코드에서

자바 배열을 오름차순으로 정렬

Arrays.sort(a);

재귀문 삭제


While 문 사용을 통해 시간을 줄였습니다


기본적인 틀은 binary search를 사용한다는 점에서 같습니다

문제에서 제시된 값이

매우 크기 때문에 조그마한 차이도 크게 느껴지는것 같습니다

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

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int []a = new int[N];

        for(int i = 0; i<N; i++){
            //Tree lengths
            a[i] = sc.nextInt();
        }

        Arrays.sort(a); // 자바 배열을 오름차순으로 정렬

        int p = 1;
        int q;
        int r = a[N-1];
        long CalculatedOutPut = 0;
        long GivenOutPut = M;

        while (p <= r)
        {
            q = (p + r)/2;
            CalculatedOutPut = 0;

            for(int i = 0; i<N; i++){
                if(a[i] >= q){
                    CalculatedOutPut += (a[i] - q);
                }
            }

            if(CalculatedOutPut >= GivenOutPut){
                p = q + 1;
            }
            else if(CalculatedOutPut < GivenOutPut){
                r = q - 1;
            }

        }

        System.out.println(r);
    }



    }

글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.