https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
잘려진 나무의 길이를 적어도 M으로 하기위한 높이의 최댓값을 구하는 문제입니다.
최적의 값을 구하는 문제이기때문에 이분탐색 중에서 파라매트릭 서치를 이용하여 해결할 수 있습니다.
높이를 1~list중 최대로 설정하여 파라매트릭 서치를 돌리고
잘려진 나무의 높이의 합이 M보다 작으면 l ~ m-1
잘려진 나무의 높이의 합이 M보다 크거나 같으면 m+1~r
로 높이를 재설정하여 구하면 됩니다.
최적의 값을 구해야하기 때문에 합이 M이라고 해서 바로 리턴해버리는 실수가 없어야합니다.
(합이 M이 나오지 않는 입력도 주어질 수 있습니다.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int list[]; static int N, M, maxheight; static long ans = 0; static void binarysearch(long l, long r) { if (l > r) return; long m = (l + r) / 2; long sum = 0; for (int i = 1; i <= N; i++) { if (list[i] <= m) continue; sum += (list[i] - m); } if (sum >= M) { ans = Math.max(ans, m); binarysearch(m + 1, r); } else { binarysearch(l, m - 1); } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); list = new int[N + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= N; i++) { list[i] = Integer.parseInt(st.nextToken()); maxheight = Math.max(maxheight, list[i]); } } public static void main(String[] args) throws Exception { input(); binarysearch(1, maxheight); System.out.println(ans); } } | cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 2110 공유기 설치 (0) | 2021.04.13 |
|---|---|
| boj 7453 합이 0인 네 정수 (0) | 2021.01.22 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |
| boj 1920 수 찾기 (0) | 2021.01.22 |
| boj 17124 두 개의 배열 (0) | 2021.01.22 |