[알고리즘풀이]백준 2805: 먹을 것인가 먹힐 것인가 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 2805번 나무 자르기를 풀었습니다. 이를 정리해보고자 합니다.

2805번: 나무 자르기

 

본문

1) 문제

2) 과정

이것도 꽤 시간이 걸렸던 문제였습니다.(한 1시간~2시간 정도)

이 문제는 main에 input과 func로 구성하여 풀었습니다. func에 output을 넣어 조금이라도 시간을 줄여보고자 했습니다.

 

2-1) main

    private static int n,m,b ;
    private static int[] intArr;
    public static void main(String[] args) throws IOException {
        input();
        func(0,b);
    }

main은 다음과 같습니다. 파라미터도 없이 차례대로 input, func를 불러냅니다.

그리고 사용할 변수를 전역변수로 선언해줍니다.

n,m,b는 각각 나무의 수, 가져가고자 하는 나무의 길이, 가장 긴 나무의 길이 입니다.

 

2-2) input()

 private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n = Integer.parseInt(strArr[0]);
        m = Integer.parseInt(strArr[1]);

        String[] strArrN = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) {
            int temp = Integer.parseInt(strArrN[i]);
            intArr[i]= temp;
            b = Math.max(b, temp);
        }
    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 n과 m에 값을 넣어줍니다. 이후 String으로 받은 나무의 길이들을 intArr에 저장하며 가장 긴 나무의 길이를 계속 b에 갱신해줍니다.

 

2-3) func()

    private static void func(int s, int f){
        if(s>f) {System.out.println(f); return;}

        int mid = (s+f)/2;
        if(testFunc(mid)) func(mid+1,f);
        else func(s,mid-1);
    }

    private static boolean testFunc(int num){
        long sum=0;
        for (int temp : intArr) {
            if(temp>num) sum+=(temp-num);
        }
        return sum >= m;
    }

func(0,b)로 func를 처음 불러줍니다. func는 나무를 찾아가는 함수이고, testFunc는 이 나무를 베었을 때 원하는 나무의 길이(m)를 넘는지 확인하는 함수입니다.

 

func는 s와 f를 받아 그 중간값인 mid를 testFunc에 넣어 해당 나무를 잘랐을 때 원하는 나무의 길이를 충당할 수 있다면, 더 줄여나가는 방향(mid+1~ f)으로 범위를 줄이고, 아니라면, 더 늘려나가는 방향(s~mid-1)로 범위를 줄여나갑니다.

 

그러다 s>f가 되어 원하는 길이의 나무를 찾으면 그 길이를 출력하며 마무리합니다. 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.binarySearch;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class BOJ2805 {
    private static int n,m,b ;
    private static int[] intArr;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr = reader.readLine().split(" ");
        n = Integer.parseInt(strArr[0]);
        m = Integer.parseInt(strArr[1]);

        String[] strArrN = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) {
            int temp = Integer.parseInt(strArrN[i]);
            intArr[i]= temp;
            b = Math.max(b, temp);
        }
    }

    private static void func(int s, int f){
        if(s>f) {System.out.println(f); return;}

        int mid = (s+f)/2;
        if(testFunc(mid)) func(mid+1,f);
        else func(s,mid-1);
    }

    private static boolean testFunc(int num){
        long sum=0;
        for (int temp : intArr) {
            if(temp>num) sum+=(temp-num);
        }
        return sum >= m;
    }

    public static void main(String[] args) throws IOException {
        input();
        func(0,b);
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/binarySearch/BOJ2805.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비