(C++) - 백준(BOJ) 1049번 : 기타줄

www.acmicpc.net/problem/1049

1049번: 기타줄

greedy문제였습니다.

 

풀이방법

 1. 패키지로 구입할 때의 최소 금액과 낱개로 구입할 때의 최소 금액을 각자 저장합니다.

 

 2. 구입 방식을 3가지로 나누어 각자 방식에 따라 금액을 구합니다.

   2-1. n개 이상으로 줄을 패키지로 구입할 때

   2-2. n개 만큼 줄을 낱개로 살 때

   2-3. n개 미만으로 최대한 패키지로 산 후 나머지를 낱개로 살 때

 

 3. 이들 중 최소값을 출력합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
using namespace std;
int n,m,case1,case2,case3;
int packageMin = INF, eachMin = INF;

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int six,one;
        cin >> six >> one;
        packageMin = min(six,packageMin);
        eachMin = min(one, eachMin);
    }
    //n개 이상으로 줄을 패키지 살 때
    if(n % 6 == 0) case1 = n / 6 * packageMin;
    else case1 = (n / 6 + 1) * packageMin;
    
    //2. n개 이상 줄을 1개씩 살 때
    case2 = eachMin * n;

    //3. n개 미만으로 최대한 6개씩 산 후 나머지를 1개씩 살 때
    case3 = n / 6 * packageMin + n % 6 * eachMin;
    cout << min({case1,case2,case3});
}