[백준] 나무꾼 이다솜 (C++)

문제

 

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

 

풀이

나무의 길이를 내림차순으로 정렬한 후, 모든 길이로 잘랐을 때, 금액을 부르트포스로 풀이했다.

 

반례

계속 3%에서 실패가 나와, 모든 반례를 찾아봤지만, 전부다 정답이었다.

문제를 다시 확인해보니 총 금액이 int 범위를 넘어 갈 수 있을거 같다고 생각했고, maxPrice의 데이터 형태를 int가 아닌 long long으로 변경했더니 맞았다.

#include<iostream>
#include<vector>
#include<algorithm>

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

using namespace std;

int n, c, w;

bool cmp(int a, int b)
{
	return a > b;
}
int main() {
	cin >> n >> c >> w;

	if (n == 0) {
		cout << 0;
		return 0 ;
	}

	vector <int> trees(n);
	for (int i = 0; i < n; i++) {
		cin >> trees[i];
	}

	sort(trees.begin(), trees.end() ,cmp);

	long long maxPrice = 0;
	for (int i = 1; i <= trees[0]; i++) {
		long long totalPrice = 0;
		for (int j = 0; j < n; j++) {
			if (trees[j] < i)
				continue;

			int treeNum = trees[j] / i;

			int price;
			if (trees[j] % i == 0)
				price = (treeNum * w * i) - ((treeNum - 1) * c);
			else
				price = (treeNum * w * i) - (treeNum  * c);

			if(price > 0)
				totalPrice += price;
		}

		if (maxPrice < totalPrice)
			maxPrice = totalPrice;
	}
	
	cout << maxPrice;

	return 0;
}