[자바] 백준 2805번: 나무 자르기

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

2805번: 나무 자르기

 

---

나무가 100만개까지 입력될 수 있기 때문에

O(n)선에서 끝내야겠다는 생각이 우선 들었다

 

우선 배열을 만들어서 나무들의 키를 입력받는다.

그리고 배열을 내림차순으로 정렬하고

순회를 시작한다.

 

h=0부터, 

첫번째 나무부터. 

나무를 h높이에서 자른 다음 sum을 자른 만큼 증가시켜준다.

 

만약 sum이 m을 초과하는 경우(나무가 남는다) 절단기를 높여야 한다.

 

(남은 나무 양/ 지금까지 나온 나무 개수)를 계산해서, 이만큼 h를 높인다.

 

이렇게 반복문을 진행하고, 더이상 절단기에 나무가 잘리지 않는다면 반복을 종료, h를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class P2805 {

	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());

		Integer[] arr = new Integer[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, Collections.reverseOrder());

		int h = 0;
		long sum = 0;
		for (int i = 0; i < n; i++) {

			int cut = arr[i] - h;
			if (cut <= 0) {
				break;
			}

			sum += cut;

			if (sum > m) {
				long over = sum - m;
				if (over / (i + 1) >= 1) {
					h += (over / (i + 1));
					sum -= ((over / (i + 1)) * (i + 1));
				}
			}
		}

		System.out.println(h);
	}

}

sum을 int로 했다가는 overflow가 발생할 수 있으니 long타입으로 선언하자.