[Java] 백준 14247 - 나무자르기

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

14247번: 나무 자르기

문제 설명

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,

나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.

참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

 

입력

첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 H_i가 n개, 순서대로 주어진다.

그 다음 줄에는 나무들이 자라는 길이 A_i가 n개, 순서대로 주어진다.

 

출력

영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

 

제한

•  1 ≤ n ≤ 100,000
•  1 ≤ H_i ≤ 100,000
•  1 ≤ A_i ≤ 10,000

풀이

정렬을 이용해 최적의 답을 찾아가는 그리디(Greedy) 문제이다.

최적해를 구하는 데에 있어 가장 중요한 사실은 "모든 나무를 한번 씩만 자르기" 이다.

자칫하면 성장 길이가 가장 큰 나무만 계속 자르면 되지 않나 생각할 수 있겠지만, 그 동안 다른 나무가 무럭무럭 자라고 있으므로 최적해가 아니다.

결국 "성장 길이" 기준으로 오름차순 정렬 후 한번씩 잘라가며 풀면 되는 쉬운 문제이다.

 

쉬운 문제인 줄 알았지만.. 간과하기 쉬운 것이 하나 있으니, 바로 타입이다.

무슨 말인가 하면..

 

100,000개의 나무의 높이가 전부 100,000으로 주어졌다고 가정해보자.

디폴트 높이의 총합만 따져도 10^10.. 무려 100억이다.. 살면서 벌 수도 만져볼 수도 없는 100억..

버릇처럼 쓰던 int는 21억따리이기 때문에 오버플로우가 날 수 있다는 점을 주의하자.. 

 

따라서 sum의 타입을 long으로 지정해주기!

전체 코드는 다음과 같다.

 

Code

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		long sum = 0;
		
		// treeinfo[x][0] : 초기 길이
		// treeinfo[x][1] : 1일 성장 길이
		int[][] treeInfo = new int[n][2]; 
		String[] input = br.readLine().split(" ");
		
		// 나무 길이 정보 
		for(int i=0; i<n; i++) {
			treeInfo[i][0] = Integer.parseInt(input[i]);
		}
		
		input = br.readLine().split(" ");
		
		// 나무 성장 정보
		for(int i=0; i<n; i++) {
			treeInfo[i][1] = Integer.parseInt(input[i]);
		}
		
		// 성장 길이 오름차순 정렬
		Arrays.sort(treeInfo, new Comparator<int[]>(){
			@Override
			public int compare(int[] tree1, int[] tree2) {
				return tree1[1] - tree2[1];
			}
		});
		
		for(int day = 0; day < n; day++) {
			sum += treeInfo[day][0] + treeInfo[day][1]*day;
		}
		bw.write(sum + "");
		br.close();
		bw.close();
 	}
}

 

 

지구 온난화가 이렇게 심각한데 이렇게 많은 나무를 잘라도 되나??