Bin_S+StudyRoom

• 문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

• 출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

• 예제 입력

4 2
12 3
15 4

10 3
20 8
40 7
60 4

15 1
100 40

17 1
12 3

7 2
10 3
12 2

9 16
21 25
77 23
23 88
95 43
96 19
59 36
80 13
51 24
15 8
25 61
21 22
3 9
68 68
67 100
83 98
96 57

• 예제 출력

12

36

300

36

12

6

• 접근방식

패키지와 단품 가격 둘 다 제일 낮은 가격을 저장하고 경우의 수중에 가장 작은 수를 고르면 된다.

1) 단품만 구매했을 경우

n * 제일 낮은 단품 가격

2) 패키지만 구매했을 경우

(n / 6) * 제일 낮은 패키지 가격

단, n % 6 != 0 즉, 6개로 나눠 떨어지지 않을 때 하나를 더 구매해야한다.

3) 패키지 + 단품을 구매했을 경우

(n / 6) * 제일 낮은 패키지 가격 + (n % 6) * 제일 낮은 단품 가격

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, package, single, result;
int min_package = 1000, min_single = 1000;

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> package >> single;
        // 패키지와 단품 가격 둘 다 제일 낮은 가격 저장
        min_package = min(min_package, package);
        min_single = min(min_single, single);
    }

    int case_1, case_2, case_3;

    case_1 = n * min_single; // 단품만 골랐을 경우 case_1
    case_2 = (n / 6) * min_package; // 패키지만 골랐을 경우 case_2
    if (n % 6 != 0) case_2 += min_package; // 나머지가 있는경우 패키지 한 번 더사기
    case_3 = (n / 6) * min_package + (n % 6) * min_single; // 단품 + 패키지를 골랐을 경우 case_3

    result = min(case_1, min(case_2, case_3));

    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1049