기타줄 (백준 - 1049번)

그리디 알고리즘 문제이다.

 

끊어진 (적어도)N개의 기타줄을 사기위한 최소 비용을 구하기 위해서는 우선 브랜드 별로 오름차순으로 정렬하여 가장 싼 패키지 가격과 가장 싼 낱개 가격을 각각 구해준다.  

 

N이 6이상일 경우 패키지 가격으로 살 것인지 아니면 낱개 가격을 살것인지를 먼저 정해야 한다. 전자의 경우 N을 6과 나누어 나온 값 만큼 패키지 가격을 곱하여 최종 가격에 더해준다. 그리고 만약에 나머지 사야할 기타줄이 있는 경우, 그 갯수와 낱개의 곱이 패키지의 가격을 넘는다면 패키지 가격을 최종 가격에 더해주고 아닌경우 (낱개가격 * 사야할 기타줄 수)를 더해준다.

 

후자의 경우에는 그냥 (낱개가격 * 사야할 기타줄 수)를 더해주면 된다.

 

코드는 다음과 같다.

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

struct price
{
	int package;
	int each;
};

bool cmp1(price& a, price& b)
{
	return a.package < b.package;
}

bool cmp2(price& a, price& b)
{
	return a.each < b.each;
}

int main()
{
	int guitarLine;
	int brands;

	cin >> guitarLine >> brands;

	price* priceInfo = new price[brands];

	for (int i = 0; i < brands; ++i)
	{
		cin >> priceInfo[i].package >> priceInfo[i].each;
	}

	// 패키지 가격 오름차순 정렬
	sort(priceInfo, priceInfo + brands, cmp1);
	int minPackage = priceInfo[0].package;
	// 낱개 가격 오름차순 정렬
	sort(priceInfo, priceInfo + brands, cmp2);
	int minEach = priceInfo[0].each;

	int result = 0;

	// 6줄이 넘는 경우
	if (6 <= guitarLine)
	{
		// 낱개로 사는게 패키지 가격보다 비싼 경우
		if (6 * minEach > minPackage)
		{
			// 패키지로 산다.
			result += (guitarLine / 6) * minPackage;
			guitarLine %= 6;
		}
		else
		{
			// 낱개로 산다.
			result += guitarLine * minEach;
			guitarLine = 0;
		}
	}

	// 패키지로 사고 사야할 기타줄 수가 남거나
	// 혹은 사야할 기타줄 수가 6줄 보다 작은 경우
	if (0 < guitarLine)
	{
		// 낱개로 사는게 패키지 가격보다 비싼 경우
		if (guitarLine * minEach > minPackage)
			result += minPackage;
		else
			result += guitarLine * minEach;
	}

	cout << result << endl;
	delete[] priceInfo;
}