백준(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;

}