BOJ 1421번: 나무꾼 이다솜

문제

---

문제 풀이

브루트포스 알고리즘

1. 오름차순으로 정렬
2. 나무의 길이를 1부터 가장 마지막 요소(최댓값)까지로 정해 탐색해 비용을 구한다.
3. 버는 비용 보다 자르는 비용이 더 크면(손해이면) 추가하지 않는다.
4. 최댓값을 구해 답을 찾는다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, c, w, t, cut = 0, cnt = 0;
    long long ans = 0, temp;
    cin >> n >> c >> w;

    for (int i = 0; i < n; i++) {
        cin >> t;
        v.push_back(t);
    }
    sort(v.begin(), v.end());

    for (int i = 1; i <= v[n-1]; i++) {
        temp = 0;
        for (int k = 0; k < n; k++) {
            cnt = (v[k] / i);
            cut = max(0, (v[k] / i));
            if (v[k] % i == 0) { cut--; }
            t = (cnt * i * w) - (c * cut);
            if (t > 0) { temp += t; } // 손해면 추가하지 않음
        }
        ans = max(ans, temp);
    }
    cout << ans;

    return 0;
}