[Java] BOJ1421_나무꾼 이다솜

www.acmicpc.net/problem/1421

1421번: 나무꾼 이다솜

---

1부터 가장 긴 나무의 길이까지 모든 나무를 잘라봐야 한다. 이때 자르는 길이보다 짧은 나무는 자를 수 없다.

자를 수 있는 모든 나무에 대해 K * L * W - (C * 자른 횟수)를 구해서 합해준 후 최댓값 비교를 한다.

 

여기서 주의할 점은 K * L * W - (C * 자른 횟수) 값이 음수가 나와서 합해줄 때 손해인 경우는 합하지 않아야한다.

위 처리를 안 해줄 경우 자르는 비용이 터무니없이 클 때 원하는 값이 안 나온다.  

 

예시 :

4 1000 1
2
1
1
1

답 : 3

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	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 C = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int max = 0;
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			max = Math.max(max, arr[i]);
		}
		int res = Integer.MIN_VALUE;
		for (int i = 1; i <= max; i++) {
			int sum = 0;
			for (int j = 0; j < N; j++) {
				int cut = 0;
				if(arr[j] >= i) {
					if(arr[j] % i == 0) cut = arr[j] / i - 1;
					else cut = arr[j] / i;
					if(W * i * (arr[j] /i) - cut * C > 0) sum += W * i * (arr[j] /i) - cut * C;
				}
			}
			res = Math.max(res, sum);
		}
		System.out.println(res);
	}

}