백준(BOJ) 1049번 기타줄
문제 : https://www.acmicpc.net/problem/1049
Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.
나의 풀이:
우선 각각 6묶음 배열과 낱개 묶음 배열을 만들어서 오름차순으로 정렬한다.
그 후 그림과 같이 알고리즘을 세운다.
코드 ( C++ )
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int sixline[50];
int oneline[50];
int main()
{
cin >> N >> M;
for (int i = 0; i < M; ++i)
cin >> sixline[i] >> oneline[i];
sort(sixline, sixline + M);
sort(oneline, oneline + M);
int sum = 0;
int line = N;
while (line > 0) {
if (line >= 6)
{
if (sixline[0] > oneline[0] * 6) {
sum += oneline[0] * line;
line -= line;
}
else {
sum += sixline[0];
line -= 6;
}
}
else
{
if (sixline[0] < oneline[0] * line)
{
sum += sixline[0];
line -= 6;
}
else
{
sum += oneline[0] * line;
line -= line;
}
}
}
cout << sum << "\n";
return 0;
}
