백준] 1049 - 기타줄

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 김지민이 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
	int n, m, sum = 0;
	int package[50], piece[50];
	bool cheap = false;

	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> package[i] >> piece[i];

	sort(package, package + m);
	sort(piece, piece + m);

	if ((double)package[0] / 6 < piece[0])
		cheap = true;
	if (cheap)
	{
		sum += n / 6 * package[0];
		n %= 6;
		if (n*piece[0] > package[0])
			sum += package[0];
		else
			sum += piece[0] * n;
	}
	else
	{
		sum = n * piece[0];
	}
	cout << sum;
}

Tip

이 문제, 약 8개월 전에 틀렸습니다를 세 번 연달아 맞고 나서 방치된 상태였다. 사실 문제 자체는 어려운 게 없다. 최대한 싸게 살 수 있는 방법으로 구현하면 되는데, 몇 가지 케이스에 유의해야 한다.

예를 들어, 구매해야 하는 제품의 개수가 패키지 하나(6개)보다 적지만, 패키지를 구매하는 게 더 저렴한 경우 이 문제를 정리해야 한다.