1049번 기타줄

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

3가지 경우로 나누면 된다.

6개 패키지 세트만 사는 경우

낱개로만 사는 경우

조합을 해서 사는 경우

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
 
vector<int> pack, piece, total(3, 0);
 
int main(void)
{
    int six_pack, pie;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &six_pack, &pie);
        pack.push_back(six_pack);
        piece.push_back(pie);
    }
 
    sort(pack.begin(), pack.end());
    sort(piece.begin(), piece.end());
 
    int Min = 2e9;
 
    total[0] = ((n + 5) / 6) * pack[0]; // 6개 패키지만 모두 살 경우
    total[1] = n * piece[0]; // 아니면 그냥 낱개로 모두 살 경우
    
    Min = min(total[0], total[1]);
 
    if (n <= 6) { printf("%d\n", Min); return 0; }
 
    int sc = 1;
 
    bool stop = false;
    total[2] = 2e9;
 
    // 6개 패키지 세트와 낱개의 조합으로 살 경우(여기서는 6개 패키지 세트이 개수가 핵심)
    while (1)
    {
        if (stop) break;
 
        int rmd = n - (sc * 6);
 
        if (rmd <= 0) stop = true, rmd = 0;
 
        total[2] = min(total[2], sc * pack[0] + rmd * piece[0]);
        Min = min(Min, total[2]);
        ++sc;
    }
 
    printf("%d\n", Min);
 
    return 0;
}