[C++]백준 - 1049번 문제

1049번: 기타줄 (acmicpc.net)

1049번: 기타줄

 

1049번 : 기타줄

---

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

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

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

구현, 그리디 문제입니다.

 

패키지 가격과 낱개 가격 중 가장 싼 가격을 골라서 가장 싸게 N개의 기타줄을 사면 됩니다.

 

모두 받아서 sort를 써도 좋고 그냥 입력 받으면서 min값을 갱신 시키는 방법으로 해도 좋습니다.

 

아무튼 가장 싼 가격의 기타줄을 써서 구입합니다.

 

그러면, 가장 싼 패키지와 가장 싼 기타줄을 구했습니다.

 

패키지는 6개의 기타줄이 들어있으므로 계산 과정은 다음과 같습니다.

 

 

1. 낱개 6개를 사는게 패키지 값보다 싸다!

-> 모두 낱개로 구입합니다.

 

2. 패키지로 사고 남은 낱개 N개를 낱개로 사는게 패키지 값보다 싸다!

-> N개는 낱개로 구입합니다.

 

3. 그냥 다 패키지로 사버리는게 싸다!

-> 모두 패키지로 구입합니다.

 

 

코드

---

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

int main() {
	int N, M;
	scanf("%d %d", &N, &M);
	
	int *packs = new int[M];
	int *units = new int[M]; 
	for(int i = 0; i < M; i++) scanf("%d %d", &packs[i], &units[i]);
	
	sort(packs, packs + M);
	sort(units, units + M);
	
    if(6 * units[0] <= packs[0]) 
    {
        printf("%d", N * units[0]);
        return 0;
    }
	
	int costs = 0;
	while(N)
	{
	    if(6 <= N)
	    {
	        costs += packs[0];
	        N -= 6;
	    }
	    else
	    {
	        if(packs[0] <= N * units[0]) costs += packs[0];
	        else costs += N * units[0];
	        N = 0;
	    }
	}
	
	printf("%d", costs);
	
	delete[] packs;
	delete[] units;
	return 0;
}

 

그 외

---