백준 온라인 저지에서 나온 문제입니다.

보물

문제 바로가기

구현 방식

stl sort를 사용하여 입력받은 수를 정렬하는 방식으로 구현했습니다.

코드

/*

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

*/

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

using namespace std;


int main()
{
	int	vecSize;
	int inputNumber;
	int total = 0;

	vector<int>	vecNumberA;
	vector<int>	vecNumberB;

	cin >> vecSize;

	vecNumberA.reserve(vecSize);
	vecNumberB.reserve(vecSize);

	for (int i = 0; i < vecSize; i++)
	{
		cin >> inputNumber;
		vecNumberA.push_back(inputNumber);
	}
	for (int i = 0; i < vecSize; i++)
	{
		cin >> inputNumber;
		vecNumberB.push_back(inputNumber);
	}

	sort(vecNumberA.begin(), vecNumberA.end(),greater<int>());
	sort(vecNumberB.begin(), vecNumberB.end(), less<int>());

	for (int i = 0; i < vecSize; i++)
	{
		total += vecNumberA[i] * vecNumberB[i];
	}
	
	cout << total << endl;

	return 0;
}

코드 해설

들어온 값들을 B는 내림차순으로, A는 오름차순으로 정렬해야 가장 적은 값이 나오는 문제입니다. 정렬을 간편하게 하기 위해서 sort함수를 사용하여 문제를 해결했습니다.

기타줄

문제 바로가기

해결 방식

그때그때 최적의 값을 고르는 그리디 알고리즘이라, 별다른 방법 없이 구현했습니다.

구현 코드

/*
https://www.acmicpc.net/problem/1049
*/


#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;



int main()
{
	int guitarString = 0;
	int brandCount = 0;
	int result = 0;


	int cheapestPackage = 99999;
	int cheapestSingle = 99999;

	int inputPackageCost;
	int inputSingleCost;


	cin >> guitarString >> brandCount;

	for (int i = 0; i < brandCount; i++)
	{
		cin >> inputPackageCost >> inputSingleCost;

		cheapestPackage = min(inputPackageCost, cheapestPackage);
		cheapestSingle = min(inputSingleCost, cheapestSingle);
	}

	if (cheapestPackage > cheapestSingle * 6)//단품가가 세트가보다 쌀 경우 바로 구매
	{
		result = cheapestSingle * guitarString;
		cout << result;
		return 0;
	}
	/*
	여기까지 왔으면 패키지가 단품보다 싸나,
	추가적으로 낱개로 구매할 상황이 나온 경우.
	*/
	while (guitarString > 0)
	{
		if (guitarString >= 6)
		{
			result += cheapestPackage;
			guitarString -= 6;
		}
		else if (cheapestPackage < cheapestSingle * guitarString)//줄의 개수가 6개 이하인데
		{
			result += cheapestPackage;
			guitarString = 0;
		}
		else
		{
			result += cheapestSingle;
			guitarString--;
		}
	}
	cout << result;

	return 0;
}

결과

랭크업 굿