[백준] 14247번 나무 자르기 자바

문제

 

14247번: 나무 자르기

 

 

문제 풀이

 

처음엔 그날 그날의 나무 중에서 가장 큰 걸 자르도록 구현했는데, 이렇게 하면 주어진 테스트 케이스도 맞추지 못한다.

 

	나무1	나무2	나무3	나무4	나무5
1일째	1	3	2	4	6
2일째	3	10	5	8	1
3일째	5	7	8	12	2
4일째	7	14	11	4	3
5일째	9	7	14	8	4

 

=> 6 + 10 + 12 + 14 + 14 = 56 이므로 최대치가 아니게 된다.

 

최대치를 구하기 위해서는 성장 속도가 제일 느린 것부터 더해주어야 한다. 왜냐하면 N일 동안 초기 길이에서 성장량이 똑같이 더해지니까 몰아서 한 번에 잘라버리는 거랑 계속 자라날때마다 바로 바로 잘라오는 거랑 값은 똑같다. 그래서 매번 최대 나무를 잘라오는 것보다 성장량이 적은 조그만 나무 값이라도 더해야 값이 더 커지게 된다.

이해하기까지 꽤 걸렸지만 이해하니 구현은 바로 쉽게 할 수 있었다.

 

 

소스 코드

 

public class b_14247 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		ArrayList<Tree> list = new ArrayList<>();
		int answer = 0;
		int n = sc.nextInt();	//나무 개수
		int[] H = new int[n];	//현재 나무 길이
		int[] A = new int[n];	//자라는 길이
		
		for(int i = 0; i < n; i++)
			H[i] = sc.nextInt();
		
		for(int i = 0; i < n; i++) {
			A[i] = sc.nextInt();
			list.add(new Tree(H[i], A[i]));
		}
		
		Collections.sort(list);
		
		for(int i = 0; i < n; i++) {
			//System.out.println(list.get(i).len + ", " + list.get(i).growth);
			answer += list.get(i).len + (list.get(i).growth * i);
		}
		
		System.out.println(answer);
		sc.close();
	}

}

class Tree implements Comparable<Tree>{
	int len, growth;
	
	public Tree(int len, int growth) {
		this.len = len;
		this.growth = growth;
	}

	@Override
	public int compareTo(Tree arg0) {
		if(this.growth > arg0.growth)
			return 1;
		else if(this.growth == arg0.growth) {
			if(this.len > arg0.len)
				return 1;
			else
				return -1;
		}
		else
			return -1;
	}
}