99클럽 코테 스터디 6일차 TIL : 이분탐색(백준 2805번)

 

백준 2805. 나무자르기

 

 

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

 

 

---

⭐나의 풀이

 

🔎문제 정리)

ex) 20 15 10 17
h = 15라고 하면, 자르면 15 15 10 15가 되고(남은나무) 
상근이가 들고가는 나무는 5와 2인 나무를 가져감 -> 총 7미터

나무를 필요한만큼만, 적어도 M미터의 나무를 집에 가져가기위해 절단기에 설정할 수 있는
높이의 최대값을 구하는 프로그램을 작성하자.

입력) 
나무의 수 N
상근이가 집으로 가져가려고 하는 나무의 길이 M
(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

나무의 높이의합은 늘 M보다 크거나 같다. 높이<10^9

출력)
적어도 M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최대값을 출력



💡 아이디어) 
1. 이분탐색 알고리즘
절단기의 길이를 left, right로 두자
- left: 문제에 제시한 대로 절단기의 길이의 최소가 1이기 때문에 1로 지정

- right: 가장 큰 나무의 길이로 절단기의 길이를 지정했을 때, 얻어갈 수 있는 나무가 없기 때문에 최대로 설정

 

✔ 최종 제출한 코드)

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);

		int n =Integer.parseInt(st.nextToken()); //나무의 수
		long m =Integer.parseInt(st.nextToken()); //상근이가 가지고싶은 나무의 길이
		
		s = br.readLine(); //다음 입력값 받기
		st = new StringTokenizer(s);
		
		List<Long> lengths = new ArrayList<>();	//나무길이들을 저장
		while(st.hasMoreTokens()) {
			lengths.add(Long.parseLong(st.nextToken()));
		}
		
		Collections.sort(lengths);	//오름차순 정렬
		
		System.out.println(searchMaxLength(n, m, lengths));
	}

	private static long searchMaxLength(int n, long m, List<Long> lengths) {
		long left = 1;
		long right = lengths.get(n-1);	//m을 나무들중 가장큰 길이로 하면 하나도 가질 수 없기 때문에 최대로 설정 
		long answer = 0;
		
		while(left<=right) {
			long mid = (left+right)/2;
			long tot = 0;
			
			for(long length:lengths) { //10 15 17 20
				if(length>=mid) {
					tot += length-mid;
				}
			}
			
			if(tot>=m) {
				answer = mid;
				left = mid+1;
			}else {
				right = mid-1;
			}
		}
		
		return answer;
	}

}

 

결과

---

 ⭐오늘의 회고

✔ answer의 초기화

문제) int answer 값을 처음에 right로 초기화 했을때, 오답 처리됨 

개선) int answer를 0으로 설정

 

사실 문제에서도 항상 나무들의 길이의 합은 m보다 클 수 없다고 하기도 했고,

개인적으로 반례를 찾을 수가 없어서 오답인게 이해가 안갔다.

chatgpt에게도 반례를 찾아달라고 했는데, 없다고했다. 

 

 

=> 이유는 못찾았지만, 0으로 초기화하는게 일반적이긴 하니까 주의하도록 하는 걸로 하자.