[백준 1049] 기타줄

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

---

해설

이번 문제는 그리디 문제이다.

 

6줄 세트의 가격 중에서 가장 싼 브랜드를 pp, 낱개 중 가장 싼 브랜드를 ii 로 두었다.

 

i) (n+1) * pp 가 n*ii 보다 작은 경우가 있을 수 있으므로 (n+1)*pp

ii) pp와 ii를 적절히 사용하는  n/6*pp + n%6*ii

iii) ii로만 n을 만드는 경우 n*ii

 

총 3가지 경우에서 최솟값을 구해주었다.

 

˙˙˙

 

소스코드

 

#include <iostream>
using namespace std;
int main(){
	int n,m; 
    cin >> n >> m;
	int pp=54321, ii=54321;
	while(m--){
		int a,b; cin >> a >> b;
		if(a<pp) pp = a;
		if(b<ii) ii = b;
	}
	cout << min((n/6+1)*pp, min(n/6*pp + n%6*ii, n*ii)) << '\n';
}