[그리디] 큰 수의 법칙

* 그리디 법칙으로 풀게된 포인트

1. 가장 큰 수를 만들어야한다.

2. 주어진 배열을 내림차순으로 정렬해야한다. (그리디는 배열의 정렬과 관련이 깊음)

3. 정렬된 배열에서 첫번째 혹은 두번째 element만 계속 더하게 되므로, 그리디 정당성을 위배하지 않는다. (= 내가 가장 고를 수 있는 큰 수만 계속 골라도 문제가 없음)

 

#include <stdio.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    clock_t start, end; //알고리즘 시간 측정하려고 쓴 것
    vector<int> vec = {2, 4, 5, 4, 6};
    int n = 5;
    int m = 8;
    int k = 3;
    bool is_same = false;
    int result = 0;
    
    start = clock();
    
    sort(vec.begin(), vec.end(), greater<int>()); // 내림차순으로 정렬
    
    if (vec[0] == vec[1]) is_same = true; // 첫째, 둘째가 같은지 확인
    
    if(is_same) {
        result = m * vec[0]; //같으면 vec[0]의 값을 m번 곱해주면 가장 최대의 값
    } else {
        int i = (m / k) * k; //vec[0]을 최대로 더해줄 수 있는 횟수
        //m에서 vec[0]을 최대로 더해줄 숫 있는 횟수를 뺀 횟수만큼 vec[1]을 더해줌
        result = (vec[0] * i) + (vec[1] * (m - i)); 
    }
    
    end = clock();
    
    
    cout << (end - start) << endl;        
    cout << (result) << endl;
    return 0;
}