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. 😓Arrays.sort 사용하는 방법 - 지양하기
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //나무의 수
int M = Integer.parseInt(st.nextToken()); //나무의 길이
int trees[] = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
trees[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(trees); //4 26 40 42 46
int start = 1;
int end = trees[N-1];
long ans = 0;
while(start <= end) {
long sum = 0; //획득한 나무의 길이
int mid = (start+end)/2;
for(int i = 0; i < N; i++) {
if((trees[i] - mid) >= 0) {
sum += trees[i] - mid;
}
}
if(sum >= M) {
start = mid + 1;
ans = Math.max(ans, mid);
}
else {
end = mid -1;
}
}
System.out.println(ans);
}
}
2. ⭐입력받을 때 시작 혹은 끝 지점 설정해주기
int start = 1;
int end = Integer.MIN_VALUE;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
trees[i] = Integer.parseInt(st.nextToken());
end = Math.max(trees[i], end);
}
나같은 경우는 end를 Integer.MIN_VALUE로 초기화해주고, 입력값을 받을 때 Math.max를 사용하여 end 지점을 최댓값으로 업데이트하도록 코드를 수정했다.
package baekjoon;
import java.util.*;
import java.io.*;
public class tmp {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //나무의 수
int M = Integer.parseInt(st.nextToken()); //나무의 길이
int trees[] = new int[N];
int start = 1;
int end = Integer.MIN_VALUE;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
trees[i] = Integer.parseInt(st.nextToken());
end = Math.max(trees[i], end);
}
long ans = 0;
while(start <= end) {
long sum = 0; //획득한 나무의 길이
int mid = (start+end)/2;
for(int i = 0; i < N; i++) {
if((trees[i] - mid) >= 0) {
sum += trees[i] - mid;
}
}
if(sum >= M) {
start = mid + 1;
ans = Math.max(ans, mid);
}
else {
end = mid -1;
}
}
System.out.println(ans);
}
}
훨씬 개선된 사실을 알 수 있다.
'Algorithms > study log' 카테고리의 다른 글
[java] 벨만포드 알고리즘 (0) | 2024.02.06 |
---|---|
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
[java] 이분탐색 (2) | 2024.01.12 |
[Algorithm] Greedy 그리디 알고리즘 (1) | 2023.12.27 |
[Algorithm] DFS, BFS (1) | 2023.12.22 |