백준 1049번 기타줄

문제 링크입니다: https://www.acmicpc.net/problem/1049

그리디(Greedy)하게 접근해서 제일 싼 브랜드 제품을 구매해야한다는 것은 누구나 알 수 있었던 문제였습니다.

하지만 패키지와 단품을 동시에 구매하는 경우 꼭 동일 브랜드에서 구매하지 않아도 되는 것이 핵심이였습니다.

알고리즘은 아래와 같습니다.

1. 패키지와 단품 가격 각각의 최소 가격을 구합니다.

2. 6개 이하인 경우 패키지 혹은 단품만 사기 때문에 패키지 vs (단품 * N)만 비교해주면 됩니다.

3. 7개 이상부터는 패키지와 단품을 섞어 사는 경우가 발생할 수 있습니다.

i) 패키지를 0부터 (N/6) + 1까지 반복문을 돌리는데 이 때 (N/6) + 1까지 반복문을 돌리는 이유는 실이 9개 필요한데 패키지 2개를 사는 경우도 있기 때문입니다.

ii) i)에서 든 예시 같은 경우가 발생하는 경우 단품의 개수를 구하는 식 N - (6*i)가 음수가 될 수 있습니다. 따라서, max(N- 6*i, 0)을 단품 가격에 곱해줘야합니다.

iii) 반복문을 돌려서 최소인 가격을 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 50;

const int INF = 987654321;

 

int N, M;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        int package = INF, unit = INF;

        //최소 패키지 가격과 단품 가격

        for (int i = 0; i < M; i++)

        {

                 int packageCost, unitCost;

                 cin >> packageCost >> unitCost;

                

                 package = min(package, packageCost);

                 unit = min(unit, unitCost);

        }

 

        //6개 이하면 package 가격과 단품 * N 사이 중 하나만 비교

        if (N <= 6)

                 cout << min(package, unit*N) << "\n";

        //패키지와 단품을 섞어 사는데 브랜드가 다를 수 있다

        else

        {

                 int result = INF;

                 //예를 들어 9개의 줄을 사야하는데 패키지 2개(6*2)를 살 수도 있으므로 (N/6) + 1

                 for (int i = 0; i <= (N / 6) + 1; i++)

                         //(위 주석과 같은 경우 (N-6*i)가 음수가 될 수 있으므로 max(N-6*i, 0)

                         result = min(result, package * i + unit * max(N - 6 * i, 0));

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~