백준 1049번: 기타줄

[문제 링크]

1049번: 기타줄

---

이 문제를 풀기 위해 필요한 정보는 패키지로 샀을 때 가장 저렴한 브랜드와, 낱개로 샀을 때 가장 저렴한 브랜드이다. 패키지 가격과 낱개 가격이 가장 저렴한 브랜드를 제외한 다른 브랜드는 고려하지 않아도 된다.

 

입력 받으면서 가장 저렴한 가격을 갱신하는 방법이 더 효율적이지만 필자는 배열에 저장한 다음 정렬하였다.

---

#include <iostream>
using namespace std;

void Quick_sort(int data[], int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] <= data[pivot])
			i++;
		while (j > start && data[j] >= data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}
		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	Quick_sort(data, start, j - 1);
	Quick_sort(data, j + 1, end);
}

int Greedy(int p[], int s[], int N, int M)
{
	Quick_sort(p, 0, M - 1);
	Quick_sort(s, 0, M - 1);

	int sum = 0;
	while (N > 0)
	{
		if (N < 6)
		{
			if (p[0] < s[0] * N)
			{
				sum += p[0];
				N -= 6;
			}
			else
			{
				sum += s[0] * N;
				N = 0;
			}
		}
		else
		{
			int pack = N / 6;
			if (p[0] * pack < s[0] * (pack * 6))
			{
				sum += p[0] * pack;
				N -= pack * 6;
			}
			else
			{
				sum += s[0] * (pack * 6);
				N -= pack * 6;
			}
		}
	}

	return sum;
}

int main(void)
{
	int single[50], package[50];

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
		cin >> package[i] >> single[i];

	cout << Greedy(package, single, N, M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 112 day