[백준 BOJ][그리디] 1049 기타줄

1049_기타줄

링크

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

 

풀이

 

브랜드마다 6개 세트의 가격, 낱개의 가격이 주어지고 최소 가격으로 구매할 방법을 찾는 문제입니다.

그렇다면 6개 세트의 가격, 낱개의 가격이 모두 다 필요하지 않겠네요. 각각 최소 가격을 구합니다.

 

n개의 줄을 사야할 때 (6개 세트 최소 가격)*(n/6) + (낱개 최소 가격)*(n%6)을 해주면 된다고 생각할 수도 있습니다.

하지만 애초에 6개 세트 최소 가격이 낱개로 6개 사는 것보다 크다면, 세트를 사는 것보다 낱개로 6개를 사는 것이 이득입니다.

또, 6개 세트 최소 가격이 낱개 최소 가격 * (n%6)보다 작다면 이것도 그냥 세트로 사는 것이 이득입니다.

 

따라서 이 두 상황을 고려해서 코드를 짜주면 됩니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

//1049_기타줄 #include <cstdio> #include <algorithm> using namespace std;   int n, m, a, b, ans;        // a 패키지, b 낱개 int amin = 1000, bmin = 1000;   int main(){     scanf("%d %d", &n, &m);       for (int i = 0; i < m; ++i){         scanf("%d %d", &a, &b);           amin = min(amin, a);         bmin = min(bmin, b);     }       if (amin < bmin * 6) ans += amin * (n / 6);     else ans += bmin * (n/6) * 6;     n %= 6;          if (amin > n*bmin) ans += n*bmin;     else ans += amin;       printf("%d\n", ans);       return 0; } Colored by Color Scripter

cs