[1040] 기타줄, c++

[1040] 기타줄

 

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

1049번: 기타줄

한줄 후기 : 저도 옜날에 기타 쳤어요.

 

기타줄을 브랜드 6개입 패키지로 사는게 더 싼지 낱개로 사는게 더 싼지 두 개를 섞어서 사는게 싼지를 고르는 문제

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int n, m, price=100000000, temp;
	int pack[51], one[51];
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d %d", &pack[i], &one[i]);
	}
	sort(pack, pack+m);
	sort(one, one+m);
	if(n > 6){
		int d = n/6;
		int one_temp = n - 6*d;
		temp = pack[0] * d + one[0]*one_temp;
		price = min(temp, price);
		
	}
	temp = one[0] * n;
	price = min(temp, price);
	temp = pack[0]*(n/6+1);
	price = min(temp, price);
	cout << price;
	return 0;
}

 

모든 가격을 다 조사할 필요는 없고, 패키지에서 가장 낮은 가격 + 낱개에서 가장 낮은 가격 으로 비교하면 된다.

그래서 입력을 sort 한 후 0번 인덱스 값들로만 비교

필요한 기타줄의 수가 6보다 크면 패키지를 여러개 사거나 패키지 + 낱개 의 조합이 있을 수 있다. 그러므로 처음에 조건문을 통해 그것을 계산한다.

이후 n의 수와 관계없이 공통적으로 있을 수 있는 낱개*n, 패키지만 사는 경우 를 계산해서 비교한다.

그리고 min 값 출력하면 됨.