백준 1421번: 나무꾼 이다솜

N개의 나무를 팔 때, 모든 나무의 길이를 같게 해야한다. 나무를 자를 때 c원이 필요하며 개당 나무의 가격을 w라 할때 벌을 수 있는 최대의 가격을 구하는 문제이다.

 

1부터 가장 긴 나무의 길이까지 모든 나무를 자르면서 조각의 수 * 가격 - 자른 횟수 * c 의 결과의 최댓값을 구한다. 자를 때, 정확히 길이로 나누어 떨어지면 조각의 갯수 -1번 자르게 되고, 아니라면 조각의 갯수 만큼 자르게 된다. 만약 나무를 잘라서 얻는 이익이 양수가 아니라면 해당 결과는 넣지 않는다(팔지 않는다).

long maxTotalProfit = 0;
for (int l = 1; l <= max; l++) {
    long currentTotalProfit = 0;
    
    for (int i = 0; i < n; i++) {
        int H = board[i];
        int numPieces = H / l;
        if (numPieces == 0) {
            continue;
        }
        
        int numCuts = (H % l == 0) ? (numPieces - 1) : numPieces;
        
        long treeProfit = (long) numPieces * l * w - (long) numCuts * c;
        
        if (treeProfit > 0) {
            currentTotalProfit += treeProfit;
        }
    }
    
    maxTotalProfit = Math.max(maxTotalProfit, currentTotalProfit);
}

 

 

결과 코드는 다음과 같다.

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

public class 나무꾼이다솜1421 {
    
    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()), w = Integer.parseInt(st.nextToken());
        int[] board = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, board[i]);
        }
        br.close();
        
        long maxTotalProfit = 0;
        for (int l = 1; l <= max; l++) {
            long currentTotalProfit = 0;
            
            for (int i = 0; i < n; i++) {
                int H = board[i];
                int numPieces = H / l;
                if (numPieces == 0) {
                    continue;
                }
                
                int numCuts = (H % l == 0) ? (numPieces - 1) : numPieces;
                
                long treeProfit = (long) numPieces * l * w - (long) numCuts * c;
                
                if (treeProfit > 0) {
                    currentTotalProfit += treeProfit;
                }
            }
            
            maxTotalProfit = Math.max(maxTotalProfit, currentTotalProfit);
        }
        
        System.out.print(maxTotalProfit);
    }
}