백준 1421번 나무꾼 이다솜 C++

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

 

나무의 길이를 자르는 길이로 나누었을 때 나누어 떨어지면 몫 - 1 이 자르는 횟수가 되고, 나누어 떨어지지 않는다면 몫이 자르는 횟수가 된다.

나무의 개수는 나무의 길이를 자르는 길이로 나누었을 때의 몫이다.

 

예) 10의 길이의 나무를 2의 길이로 자를 때 : 2 | 2 | 2 | 2 | 2  -> 10 / 2 - 1 = 4  - > 4번 자름, 나무 5개 나옴

     10의 길이의 나무를 3의 길이로 자를 때 : 3 | 3 | 3 | 1      -> 10 / 3 = 3  -> 3번 자름, 나무 3개 나옴

 

이것을 이용해서 자르는 길이를 1부터 나무의 최대 길이까지 전부 탐색하면서 가격을 구하는데, 중간에 잘라서 팔았을 때 손해가 나오는 경우는 자르지 않고 그냥 넘어간다.

 

처음에 계속 틀렸다고 하길래 뭐가 빠진건지 고민을 많이 했는데, 생각해보니 10000 * 10000 * 50 이 50억이라 int 범위를 넘어가서 int가 아닌 long long으로 범위를 늘리니 맞았다..

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

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

	int n, c, w;
	cin >> n >> c >> w;
	vector<int> woods(n);
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		cin >> woods[i];
		maxLength = max(maxLength, woods[i]);
	}
	ll maxMoney = 0;
	for (int length = 1; length <= maxLength; length++) {
		ll totalSliceCnt = 0;
		ll totalWoodCnt = 0;
		for (int i = 0; i < n; i++) {
			ll sliceCnt = woods[i] % length == 0 ? woods[i] / length - 1 : woods[i] / length;
			ll woodCnt = woods[i] / length;
			if (woodCnt * length * w - sliceCnt * c < 0) continue;
			totalSliceCnt += sliceCnt;
			totalWoodCnt += woodCnt;
		}
		ll money = totalWoodCnt * length * w - totalSliceCnt * c;
		maxMoney = max(maxMoney, money);
	}
	cout << maxMoney;
};