[백준] 1421 - 나무꾼 이다솜

처음에 버릴 수 있는 부분이 있는걸 모르고 헤맸습니다...

 

말그대로 브루트 포스!!

 

1. 1~10000길이만큼 잘라서 얻을 수 있는 각각의 나무의 값을 tmp배열에 저장

 

2. 내림차순 정렬

 

3. 앞에서 부터 더하며 이전까지 더한 것이 지금값과 더했을때 보다 크다면 break

 

4. 최대값과 비교하여 갱신

 

#include <iostream>
#include <algorithm>
#define MX 1002
using namespace std;
 
int arr[MX];
int N, C, W, dab, lim = 987654321;
 
bool com(const int i, const int j)
{
    return i > j;
}
 
int main(void)
{
    cin >> N >> C >> W;
 
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        if (arr[i] < lim) lim = arr[i];
    }
 
    for (int i = 1; i <= 10000; i++)
    {
        int tmp[MX] = { 0 };
        for (int j = 0; j < N; j++)
        {
            if (arr[j] % i) tmp[j] = W * arr[j] - W * (arr[j] % i) - C * (arr[j] / i);
            else tmp[j] = W * arr[j] - C * (arr[j] / i - 1);    
        }
        sort(tmp, tmp + N, com);
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            if (sum + tmp[j] < sum) break;
            sum += tmp[j];
        }
        if (sum > dab) dab = sum;
    }
    cout << dab << endl;
 
    return 0;
}