[ 백준 1421 ] 나무꾼 이다솜 (c/c++)

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

 

 

[ 문제 요약 ]

첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 나무를 팔 때는 같은 길이만 팔 수 있다. 작업장에서 나무를 한 번 자를 때는, C원이 든다. 그리고, 지역 목재상에서 나무를 살 때는, 한 단위에 W원씩 줄 때, 벌 수 있는 돈의 최댓값을 출력한다.

 

 

[ 문제 풀이 ]

1. 나무를 잘라서 팔 때 같은 나무를 여러 번 자를 수 있기 때문에 잘라서 팔 나무의 높이를 정한 뒤 모든 나무를 같은 높이로 잘라서 판다.

2. 만약 잘라서 파는 것보다 자르는 비용이 높으면 더하지 않는다.

3. 하나의 나무를 자를 때 만약 정확하게 나눌 수 있으면 자르는 횟수는 나무의 갯수 - 1이 되고 그렇지 않다면 나무의 갯수와 동일하다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, C, W;
int arr[1010];
long long ans;

int main() {
    cin >> N >> C >> W;
    for (int i=0; i<N; i++){
        cin >> arr[i];
    }
    sort(arr, arr+N);
    for (int i=1; i<=arr[N-1]; i++){
        long long cnt = 0, cost = 0;
        for (int j=0; j<N; j++){
            if (i == arr[j]) cost += i * W;
            else if (i < arr[j]){
                if (arr[j] % i == 0) cnt = -1;
                else cnt = 0;
                if (((arr[j] / i) + cnt) * C < (i * W) * (arr[j] / i)){
                    cost -= ((arr[j] / i) + cnt) * C;
                    cost += (i * W) * (arr[j] / i);
                }
            }
        }
        ans = max(ans, cost);
    }
    cout << ans;
    return 0;
}

 

 

[ 주의할 점 ]

나무를 자르는 횟수와 나무의 가격에 주의해야 한다.