728x90
반응형
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
int[] arr = new int[n];
int max = 0;
int start = 0;
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if (max < arr[i]) {
max = arr[i];
}
}
int end = max;
while (start <= end) {
long total = 0;
int mid = (start + end) / 2;
for (int i = 0; i < n; i++) {
if (arr[i] > mid) {
total += arr[i] - mid;
}
}
if (total < m) {
end = mid - 1;
} else {
start = mid + 1;
}
}
System.out.println(end);
br.close();
}
}
|
cs |
메모리 초과의 덫에 걸리다..!
이 문제는 메모리초과 때문에 정말 많이 애 먹었다. 사실 랜선 자르기 문제랑 그냥 완전 똑같은데 왜 메모리 초과에 그렇게 많이 걸렸는진 나도 잘 모르겠다. 그래서 내가 메모리 초과를 해결하기 위해 썼던 방법이 2가지 있는데
1) Scanner -> Buffered Reader로 바꿔줬고
2) 무엇보다 total값의 자료형을 long으로 고쳐주는 게 중요했다.(얘는 int범위를 넘어갈 수도 있기 때문이다)
그 외 start,end,arr은 굳이 long으로 해주지 않아도 됐다.
어차피 이 문제는 랜선 자르기 문제와 동일한데, 이 문제에서 알아야하는걸 살펴보면
for (int i = 0; i < n; i++) {
if (arr[i] > mid) {
total += arr[i] - mid;
}
}
여기서 arr[i] >mid의 조건문이다. 반드시 arr[i]가 mid보다 커야 한다. 등호도 상관없을 것 같긴한데
굳이 total에 0을 붙여줘야하나 싶다. 음수일 경우, total값이 변질된다. 무엇보다 절단기보다 나무의 길이가
빫으면 자를 수가 없다..ㅋㅋㅋㅋ 그래서 부등호를 꼭 붙여줘야한다.
end<start가 될때까지 이진탐색을 한다는건 알아두자.
728x90
반응형
'알고리즘 > 이진탐색' 카테고리의 다른 글
| [java 백준] 골드 5/ 2110번 공유기 설치 (0) | 2022.01.26 |
|---|---|
| [java 백준] 실버 4/10816번 숫자카드 2 (0) | 2022.01.26 |
| [java 백준] 실버 4/10815번 숫자카드 (0) | 2022.01.24 |
| 이진탐색 알고리즘 (0) | 2022.01.22 |
| [java 백준]실버 3 /1654번 랜선 자르기 (0) | 2022.01.22 |
댓글