-
[백준] 2805 나무 자르기 - Java알고리즘 문제 풀이 2024. 4. 18. 00:22
문제 - 나무 자르기
난이드 - 실버 2
https://www.acmicpc.net/problem/2805
문제 설명
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
예제 입력
4 7 20 15 10 17
예제 출력
15
접근 방법
- 시간 제한이 1초라 반복문 2개 이상으로 해서 풀면 안될 것 같다 -> 반복문 2개 이상으로 완전 탐색이 아니라 이분 탐색으로 해서 풀어야 될 것 같다
- 우선 리스트를 오름차순으로 정렬을 하고 최소 0 부터 최대 값을 구해야 한다 -> 입력 받은 값 중에 제일 큰 수
- 0~ 입력 받은 값 중에 제일 큰수 / 2 이렇게 mid 값을 구한후 리스트 요소 가 mid 값 보다 크면 뺄셈을 해주고 그 결과값을 더 해준다
- 뺄셈을 한 후 다 덧셈을 해준후 M과 비교했을때 M이 더 크면 mid 값을 줄여야 하고 M이 더 작으면 mid 값을 증가 시켜주는 식으로 풀어야 할 것 같다
코드 작성
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); List<Integer> list = new ArrayList<>(); st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { list.add(Integer.parseInt(st.nextToken())); } list.sort(Comparator.comparingInt(Integer::intValue)); int min = 0; int max = list.get(list.size() - 1); while (min <= max) { int mid = (min + max) / 2; long qwer = 0; for (int value : list) { if (value > mid) { qwer += (value - mid); } } if (qwer < M) { max = mid - 1; } else{ min = mid + 1; } } System.out.println(max); } }
풀고 느낀점
1. 이 문제도 일반적인 이분 탐색 문제 인 것 같다
2. 이 문제에서 핵심은 남은 나무의 길이와 M과 비교했을때 max와 min 값을 어떤식으로 조절 해줘야 하는지가 핵심인 것 같다
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] H-Index -Java (0) 2024.04.19 [백준] 1654 랜선 자르기 -Java (1) 2024.04.18 [백준] 19637 IF문 좀 대신 써줘 - Java (0) 2024.04.18 [백준] 2512 예산 - Java (0) 2024.04.17 [프로그래머스] 모의고사 - Java (0) 2024.04.15