[1049] 기타줄

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

1049번: 기타줄

 

---

 

🔎 해결 방법

정렬을 한 후 제일 첫번째 원소를 취하던지, 아니면 입력받을 때마다 비교를 하던지 해서

패키지 가격의 최솟값과 낱개 가격의 최솟값을 찾아야 한다.

그리고 이 두 개의 값만 사용하면 문제를 풀 수 있다!

 

1. 모두 낱개로 사는게 제일 싼 경우

예를 들어 가장 싼 패키지 가격이 24, 가장 싼 낱개의 가격이 3이라면

항상 낱개로 사는 것이 더 이득이다.

따라서 (가장 싼 낱개 가격)(piece[0]) * (구매해야 하는 카드의 개수)(n) 가 답이 된다!

 

2. 위의 경우가 아닌 경우

이때는 또 두 가지를 비교해봐야 한다.

1) 구매해야 하는 카드보다 더 많이 구매한 경우(only 카드팩)

ex) pack[0] = 100, piece[0] = 40, n = 15이라면

카드 팩 3개를 구매하는것이 가장 이득이다.

따라서 답은 100*3 = 300

 

2) 구매해야 하는 카드의 개수에 딱 맞게 구매하는 경우(카드팩 + 낱개)

ex) pack[0] = 20, piece[0] = 4, n = 10이라면

카드 팩 1개를 구매한 후, 남은 4개의 카드만 낱개로 구매하는 것이 제일 이득이다. 

따라서 답은 20 + 4*4 = 36

 

위의 두 경우를 고려하여 더 작은 값을 답으로 출력하면 끝!

 

---

 

✏️ 내 코드(C++)

// [1049] 기타줄
// https://www.acmicpc.net/problem/1049
// 그리디 알고리즘

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

int main(void)
{
    int n, m, tmp1, tmp2;
    vector<int> pack;
    vector<int> piece;
    scanf("%d %d", &n, &m);
    for(int i = 0 ; i < m ; i++) {
        cin >> tmp1 >> tmp2;
        pack.push_back(tmp1); piece.push_back(tmp2);
    }

    sort(pack.begin(), pack.end());
    sort(piece.begin(), piece.end());

    // 모두 낱개로 사는게 제일 싼 경우
    if(pack[0] > 6 * piece[0]) { 
        cout << piece[0] * n; 
    }

    // 팩으로 최대한 사고 남은 것은 낱개로 사는 경우 vs 모두 팩으로 사는 경우
    else {
        cout << min((n / 6) * pack[0] + (n % 6) * piece[0], (int)ceil((double)n/6) * pack[0]) << endl;
    }
    return 0;
}