1049 기타줄

1049. 기타줄 / c++ / Silver4 / 20분

문제

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

1. 새로 사야할 기타 줄 N개와 기타줄 판매 업체 수 M개가 주어진다. (1 <= N <= 100), (1 <= M <= 50)
2. 각 판매 업체마다 6개들이 가격과 1개들이 가격이 다를 때, 적어도 N개를 살 수 있는 최소 가격은? (가격은 0 이상, 1’000 이하)

접근 방식

그리디

1. 6개들이와 1개들이를 각각 벡터에 저장하여 정렬하려고 생각했다.
2. 그런데 생각하다보니 굳이 다른 가격을 저장할 필요 없이 6개들이와 1개들이의 최저가들만 저장하면 된다는 사실을 깨달았다.
3. 만약 1개들이 가격 * 6이 6개들이 가격보다 작거나 같다면, 고민할 필요없이 N개만큼 사면 될 일이었고,
4. 6개 가격보다 크다면, 일단 6의 배수만큼은 6개들이 가격만큼 사고,
5. 그 후 남은 갯수 * 1개들이 가격과 6개들이 가격을 다시 비교하여 더 싼쪽으로 사면 해결

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>

using namespace std;
inline int Min(int A, int B) {return A < B ? A : B;}

int N, M, num;
int onePrice, sixPrice;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> N >> M;
    
    for (int i = 0; i < M; ++i)
    {
        if (i == 0)
        {
            cin >> sixPrice >> onePrice;
        }
        else
        {
            cin >> num;
            sixPrice = Min(sixPrice, num);
            cin >> num;
            onePrice = Min(onePrice, num);
        }
    }
    
    int totalPrice;
    if (onePrice * 6 <= sixPrice)
    {
        totalPrice = N * onePrice;
    }
    else
    {
        totalPrice = (N / 6) * sixPrice;
        int remain = (N%6);
        if (remain > 0)
        {
            totalPrice += Min(sixPrice, onePrice * remain);
        }
        
    }
    
    cout << totalPrice << '\n';
    
    return 0;
}

다시 생각해 볼 점

1. 가장 싼 가격들만 저장하면 된다는걸 깨닫는게 중요했다. (그리디는 항상 최소 혹은 최대만 필요하기 때문에)
2. 조건을 검사할 때 세분화하여 잘 처리하는 것이 중요했다.
   1. 1개들이로 다 사도 되는경우
   2. 6개들이를 살 필요가 있는 경우
      1. 남은 갯수도 6개들이로 사야하는 경우
      2. 남은 갯수는 1개들이로 사야하는 경우
3. 실버4라 그런지 큰 무리없이 한번에 클리어