문제

문제 설명

플로리스트가 자신의 이윤을 극대화 하기 위해서 가격에 소비자가 원래 꽃의 갯수에 1을 다하여 파는 식이다.
예를 들어서 (0+1) x original price 다음 꽃의 가격은 (1 + 1) x original price 이런식으로 계산한다. 예를 들어서 만약에 k는 친구 인원수 k = 3이면 n은 꽃의 갯수 n = 4, 원래 가격은 c = [1, 2, 3, 4]가 되어야하는데 각각의 친구는 [2, 3, 4]가격의 꽃을 사게 되는 것이다. 세 명이 모두 구매하게 될때는 원가의 모든 꽃을 구매할 수 있고, 원래 인원보다 작게되면 문제에서 주어진 연산방식을 따라야 한다.
쉽게 주어진 예를 보고 설명을 하면,
ex1)
3 3이 input으로 주어지면 3개의 꽃을 3명의 사람이 산다는 의미이고 여기서 cost는 꽃의 갯수 3개가 생긴다.
cost = [1, 2, 3]이라면
즉 3명이 1개씩 사면 되서 최소 가격은 1 + 2 + 3이 된다.

ex2)
10 3
1 2 3 4 5 6 7 8 9 10
이런식으로 주어진다면, 10개의 꽃을 모두 사야하는데 최소비용을 지불하고 사려면 가장 큰 꽃부터 차례로 한 개씩 사고 나머지는 돈을 더 지불하고 사는 방식이다.
계산 과정)
10 + 9 + 8 + 7(1+1) + 6(1+1) + 5(1+1) + 4(1+2) + 3(1+2) + 2(1+2) + 1*(3+1)

문제 해결 전략

우선 내림차순으로 정렬한 후에 만약 인원수와 꽃의 수가 같다면 한 개씩 사면 되기 때문에 추가적인 연산은 불필요하다. 내림차순으로 정렬된 가격을 인원수와 나누어 떨어지는 숫자가 나올때마다 원래 한개 가격을 곱하기 전에
내가 샀던 꽃의 갯수만큼 더해주는 방식이기 때문에 그것을 inner loop에 넣어서 증가시켜준 상태로 연산하면 될 것 같다.

코드

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

int getMinimumCost(int k, vector<int> c){
	int min = 0;
	int p = 1;
	if(k == c.size()) return accumulate(c.begin(), c.end(), 0);
	sort(c.begin(), c.end(), greater<>());
	for(int i = 0;i < c.size();i++){
		int l = 0;
		if(i % k == 0) p++;
		for(int j = 0;j < p-1;j++) l++;
		min += c[i]*l;
		cout << i << " "<< l << endl;
			
	}
	return min;
}

코드를 이해하기 쉽게 짜긴 했지만 더 간결하게 만들면 iner for문을 제거하고 p로만 연산을 해도 연산이 가능하다.!!