백준 문제 풀이 - 기타줄 1049번

📜 문제 이해하기

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.
끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

💡 문제 재정의

각 브랜드별로 6개 패키지 가격과 낱개 패키지 가격이 주어질 때 끊어진 기타줄을 최소한의 금액으로 사자.

✏️ 계획 수립

먼저 각 패키지와 낱개들의 가격들중에서 가장 싼 가격들을 저장한다.
그 후 패키지만으로 사기, 패키지와 낱개로 사기, 낱개만으로 사기를 전부 계산해 본 뒤 그중에서 가장 싼 금액을 출력한다.

💻 계획 수행

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int N, M, package_price, piece_price;
    cin >> N >> M;
    double min_price = 1001 * N;
    int min_package_price = 1001, min_piece_price = 1001;
    int package_num, piece_num;

    for(int i=0; i<M; i++){
        cin >> package_price >> piece_price;
        if (package_price < min_package_price)
            min_package_price = package_price;
        if (piece_price < min_piece_price)
            min_piece_price = piece_price;
    }

    // 패키지만으로 사기
    package_num = ceil(N / 6.0);
    if(package_num * min_package_price < min_price)
        min_price = package_num * min_package_price;

    // 패키지 + 낱개
    package_num = floor(N / 6.0);
    piece_num = N % 6;
    if(package_num * min_package_price + piece_num * min_piece_price < min_price)
        min_price = package_num * min_package_price + piece_num * min_piece_price;

    // 낱개만으로 사기
    if(min_piece_price * N < min_price)
        min_price = min_piece_price * N;

    cout << min_price << endl;
}

🤔 회고

가장 싼 금액을 출력하기 위해서 그리디 알고리즘으로 접근했다. 현재의 조건에서 가장 좋은 값을 찾는 문제이기에 그리디 알고리즘이 적합하다.