[백준][C++] 1049: 기타줄

문제

1049번: 기타줄

풀이

그리디

 

기타 줄을 사는 경우는 총 3가지이다. 

1. 패키지만 사서 N줄을 채우는 경우
2. 낱개만 사서 N줄을 채우는 경우
3. 패키지와 낱개 혼합으로 사서 N줄을 채우는 경우

여기서 필요한 값은 패키지 가격의 최솟값, 낱개 가격의 최솟값이다. 3번의 경우 최솟값인 패키지를 (N / 6)개 구입해서 남은 줄인 (N % 6)줄을 낱개로 구입하는 것이 가격이 최소다.

위의 3가지 경우 중에서 최솟값을 구한다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    int six_mini = INT_MAX;
    int per_mini = INT_MAX;

    for (int i = 0; i < M; ++i)
    {
        int temp1, temp2;
        cin >> temp1 >> temp2;

        // 6줄 패키지 최솟값, 1줄 최솟값
        six_mini = min(six_mini, temp1);
        per_mini = min(per_mini, temp2);
    }

    // 패키지만 산 경우, 낱개로 산 경우, 패키지와 낱개 혼합으로 산 경우 중 최솟값을 구한다.
    int answer = six_mini * (N / 6 + 1);
    answer = min(answer, per_mini * N);
    answer = min(answer, six_mini * (N / 6) + per_mini * (N % 6));

    cout << answer;

    return 0;
}