[백준/C,C++] 1049번: 기타줄

www.acmicpc.net/problem/1049

1049번: 기타줄

풀이

살짝 헷갈리는 문제입니다.

 

경우를 잘 따져야 하는데요.. 크게 2가지로 나눌 수 있습니다.

 

패키지 가격보다 낱개 6개의 가격이 더 낮은 경우, 낱개로 모두 구매하는 것이 최소 가격입니다.

 

하지만 패키지 가격이 낱개 6개의 가격보다 더 낮은 경우가 중요합니다.

 

어쨌든 필요한 기타 줄이 6개 이상이라면 그만큼은 무조건 패키지를 사는 것이 최소 가격일 겁니다.

 

하지만 패키지를 살 수 있는 만큼 모두 구매한 후

 

남은 필요 기타 줄이 6개 미만이라면 비교 대상이 달라지는데

 

낱개가격 * 남은 필요 기타 줄과 패키지 가격을 비교해서 남은 개수를 채워야 합니다.

 

#include<iostream>

using namespace std;

int main(void)
{
    int n, m; cin >> n >> m;
    int package = 100000, piece = 100000;
    int res = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) {
            int tmp; cin >> tmp;
            if (j == 0) {
                package = min(package, tmp);
            }
            else {
                piece = min(piece, tmp);
            }
        }
    }

    if (n >= 6) {
        if (package < piece * 6) {
            res += (n / 6) * package;
            n = n - ((n / 6) * 6);
        }
        else {
            res += n * piece;
            n = 0;
        }
    }

    if (n != 0) {
        package < piece* n ? res += package : res += piece * n;
    }

    cout << res;

    return 0;
}

반례

Input

7 1

100 99

Output

199

 

Input

23 3

50 25

70 28

60 20
Output

200