2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
접근하기
구하는 것 : 원하는 길이만큼의 나무를 가져가기위해 설정해야 하는 절단기의 높이
1. 위에서부터 자르면서 잘린 나무들의 길이의 합과 목표값을 비교한다.
2. 나무들의 길이는 배열에 넣는다
3. 나무길이의 최댓값을 알아야 한다. 모든 배열요소에 방문하면서 1씩 증가하면서 자르고, 자르면서 나무 길이의 합을 구한다.
4. 나무 길이 합과 목표값이 같으면 출력
코드
import java.util.Scanner;
public class Practice {
public static void main(String[] args) {
Scanner scan= new Scanner(System.in);
int N=scan.nextInt();
int M=scan.nextInt();
//N개의 나무들에 각각 길이를 저장하는 배열
int heights[] = new int[N];
for(int i=0;i<N;i++) {
int a=scan.nextInt();
heights[i]=a;
if(heights[i]<0||heights[i]>=1000000000) {
System.out.println("나무의 길이는 0 이상 1,000,000,000 미만이어야 합니다.");
return;
}
else {
continue;
}
}
//가장 긴 나무길이 찾기
int max=heights[0];
for(int i=0;i<N;i++) {
if(max<heights[i]) {
max=heights[i];
}
}
//자르기 시작 : i를 0부터 1씩 증가시키면서 조건에 맞게 자르고, 잘린 나무들의 합이 M과 같으면 출력 및 종료
int h=0;
for(int i=0;i<=M;i++) {
int sum=0;
for(int j=0;j<N;j++) { //배열 요소 방문
if(max-i<heights[j]){
sum+=(heights[j]-(max-i));
//System.out.println(i+" "+j+" "+sum);
}
}
if(sum==M){
System.out.println("절단기의 높이는 "+(max-i));
}
//System.out.println();
}
}
}알게된 것 : 1씩 증가하면서 원하는 길이만큼 얻어내는 방식으로 접근했더니 시간초과가 나왔다. 연산 수를 줄여야 한다.
접근하기2 - 이진 탐색
1. 중앙값 mid을 이용한다.
2. 나무길이 최대값을 max라고 하면 최초의 중앙값 mid = (0+max)/2 이다.
3. 중앙값으로 자른 위쪽의 나무들의 길이합을 더하고 목표값과 비교한다.
4. 길이합 < 목표값이면 절단기 높이는 더 아래로 내려가야 한다. 새로운 중앙값이 필요하므로, max = mid로 바꾸고 다시 mid = (0+max)/2로 갱신한다.
5. 길이합 > 목표값이면 절단기 높이는 더 위로 올라가야 한다(나무 길이 합이 줄어야 하므로).
최초에 0~max사이의 중앙값이었다면 새로운 중앙값은 mid = ((mid+1)+max)/2 로 한다.
mid+1인 이유는 mid일때는 이미 비교했기 때문이다.
6. 길이합 == 목표값이면 끝낸다. 이때 mid가 절단기 높이이다.
7. 이때 min변수를 추가로 설정하면 더 알아보기 쉬울 것 같다.
다시 접근하기
1. 중앙값 mid를 이용할거고, mid의 결정을 위해 최초의 min=0, max=최대 나무길이
2. 길이합 < 목표값이면 max = mid (상한값 낮춤 : 상한값을 중앙값으로 갱신)
3. 길이합 > 목표값이면 min = mid+1 (하한값 올림 : 하한값을 중앙값+1로 갱신)
4. 반복은 min < max 동안 한다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan= new Scanner(System.in);
int N=scan.nextInt();
int M=scan.nextInt();
int min=0,max=0;
//N개의 나무들에 각각 길이를 저장하는 배열
int heights[] = new int[N];
for(int i=0;i<N;i++) {
heights[i]=scan.nextInt();
if(max<heights[i]) { //가장 긴 나무길이 찾기
max=heights[i];
}
}
//자르기 시작 : 이진탐색
//상한과 하한의 중앙값에서 자르고 그 윗부분을 더한다. 따라서 최초의 하한은 0이지만 윗부분을 더한것이 목표값보다 크면 하한을 중앙값+1로 업데이트한다.
//종료시점 : sum==M일때 하한이 중앙값+1로 갱신되고, 이때 상한은 중앙값이므로 하한>상한이게 돼서 종료된다.
while(min<max) { //길이가 부족하다 == 하한기준을 중앙값+1로 업데이트해서 다시 자른다.
int mid=(max+min)/2; //mid값 초기화
long sum=0; //sum 초기화
for(int tree_height: heights) { //for-each문으로 배열 요소 방문하면서 더합
if(tree_height>mid) { // 자르는위치(중앙값)보다 나무 길이가 길어야됨
sum+=tree_height-mid;
//System.out.println(sum);
}
}
if(sum<M) { //더한 것이 목표값보다 작으면 상한을 중앙값으로 업데이트
max=mid;
}
else { //더한 것이 목표값보다 크면 하한을 중앙값+1로 업데이트
min=mid+1;
}
}
System.out.println(min-1);
}
}알게된 것 : 1,000,000,000미만이므로 sum 선언을 int로 하면 틀린다. long으로 해야함
참고한 블로그
'백준' 카테고리의 다른 글
| 백준 1874 파이썬 (0) | 2022.01.25 |
|---|