[baekjoon] 1049 : 기타 (C++)

문제

---

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

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

 

예제 입출력

---

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

1049번: 기타줄

 

문제 풀이

---

먼저 비용이 가장 적게 들도록 하기 위해 낱개의 가격중 가장 싼값과 패키지의 가격중 가장 싼 가격을 k, j라는 변수에 넣는다.

다음 모든 경우의 수를 정해야 하는데 전부 낱개로 산 가격, 하나만 패키지로 산 후 나머지는 전부 낱개로 산 가격, 끊어진 기타줄이 6의 배수가 아니어도 전부 패키지로 산 가격이 있다. 이것을 for문으로 돌려 패키지의 갯수가 0개일때부터 (N/6)+1번(전부 패키지로 산 횟수)까지 돌려준다.

하지만 N이 6이 넘지 않는 경우 N - (6 * i)가 마이너스값이 되므로 따로 if문으로 분리 해주면 된다.

 

최종 코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> pp, sp;
	int p, s;
	vector<int> total;
	for (int i = 0; i < M; i++) {
		cin >> p >> s;
		pp.push_back(p);
		sp.push_back(s);
	}
	int k = *min_element(sp.begin(), sp.end()); // 가장 싼 낱개의 가격
	int j = *min_element(pp.begin(), pp.end()); // 가장 싼 패키지의 가격
	for (int i = 0; i <= (N / 6) + 1; i++) {
		int a = j * i + (N - 6 * i) * k;
		if ((N - 6 * i) < 0)
			total.push_back(j * i);
		else
			total.push_back(a);
	}
	int answer = *min_element(total.begin(), total.end());
	cout << answer;
}