[백준] 2805번 나무 자르기 (투포인터_JAVA)

int 범위 잘못봐서 틀린사람 바로 나!

...

문제를 꼼꼼히 읽자고 아무리 다짐해도

왜 자꾸 이런 거에서 틀리는지

 

그래도 9개월 전에 틀린 문제

오늘 맞혀서 기분이 굉장히 좋다!

 

 

---

문제

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 투포인터

나무의 개수가 백만 이하여서, 완전탐색은 시간초과가 발생할 것이라 생각했다.

그래서 고민하다가, 문득 산하언니가 비슷한 문제를 투포인터로 풀었다고 설명해준 게 생각나서 투포인터로 풀었다.

확실히 투포인터로 풀으니 시간이 많이 줄었다.

 

풀이 과정

1.

나무의 개수와 가져가고 싶은 나무의 길이를 입력받는다.

여기서 중요한 점은 나무의 길이가 20억 이하로 입력될 수 있으므로 int가 아닌 long으로 입력받아야 한다.

 

2.

각각의 나무의 길이를 입력받기 위해 배열 tree를 생성하고 입력받는다.

가장 긴 나무의 길이를 알기 위해 입력받을 때마다 max를 갱신시킨다.

 

3.

min은 0, max는 가장 긴 나무의 길이로 설정한다.

그리고 min이 max보다 작거나 같을 때만 반복문을 실행하도록 조건을 만들고, 중간값 mid를 구한다.

이 mid값이 나무를 자르는 높이다.

 

4.

mid를 기준으로 나무를 잘랐을 때의 나무의 길이 합인 sum을 구한다.

 

이 sum의 값이 원하는 길이인 length보다 작다면, 더 작은 높이로 잘라야 하므로 max값을 mid-1로 갱신해준다.

만약 sum의 값이 원하는 길이와 같거나, 크다면 더 높게 자르는 것을 시도할 수 있으므로 min값을 mid+1로 갱신한다.

또한, answer의 값을 mid와 비교한 후 더 큰 값으로 answer을 갱신한다.

왜냐하면 우리는 원하는만큼만 나무를 자르고 싶기 때문에, 나무를 자르는 높이가 높을 수록 좋기 때문이다. 

 

5.

반복문이 종료되면 가장 최적의 높이인 answer를 출력한다

 

 

---

코드

 

import java.util.Arrays;
import java.util.Scanner;

public class Test_2805_나무자르기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();			//나무의 개수
		long length = sc.nextLong();	//가져가고 싶은 나무의 길이
		
		long min = 0;
		long max = 0;
		
		long[] tree = new long[n];
		for(int i=0; i<tree.length; i++) {
			tree[i] = sc.nextLong();
			if(max<tree[i]) max = tree[i];
		}
		
		long answer = 0;
		
		//투포인터
		while(min<=max) {
			long mid = (min+max)/2;
			
			long sum = 0;
			for(int i=0; i<tree.length; i++) {
				if(mid <= tree[i]) sum+=(tree[i]-mid);
			}	
			
			if(sum<length) max = mid-1;			//원하는 만큼 나무가 잘리지 않았을 때
			else {								//원하는 것 이상 나무가 잘렸을 때
				min = mid+1;
				answer = Math.max(mid, answer);
			}
		}
		
		
		//출력
		System.out.println(answer);
				
	}
}

 

 

(❁´◡`❁)

끝!