그리디 알고리즘

11399번 문제 : ATM

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main() 
{
    int num;
    cin >> num;
    
    for (int i = 1; i <= num; i++)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
    }
 
    sort(v.begin(), v.end());
 
    for (int i = 1; i < v.size(); i++)
    {
        v.at(i) += v.at(i - 1);    
    }
 
    int sum = 0;
    for (auto i : v)
        sum += i;
 
    cout << sum << endl;
 
 
    return 0;
}

11047번 문제 : 동전0

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main() 
{
    int num, sum;
    cin >> num >> sum;
 
    for (int i = 0; i < num; i++)
    {
        int inp;
        cin >> inp;
 
        v.push_back(inp);
    }
    
    int counter = 0;
    
    for (int i = v.size() - 1; i >= 0; i--)
    {
        while (true)
        {
            int temp = sum - v.at(i);
            if (temp >= 0)
            {
                sum -= v.at(i);
                counter++;
            }
            else
                break;
        }
        if (sum == 0)
            break;
    }
 
 
    cout << counter << endl;
 
    return 0;
}

2217번 문제 : 로프

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int main()
{
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        int input;
        cin >> input;
        v.push_back(input);
    }
 
    sort(v.begin(), v.end(), greater<int>());
 
    int maxWeight = 0;
    if (v.size() >= 2)
    {
        for (int i = 0; i < v.size() - 1; i++)
        {
            int weight = 0;
            if (v.at(i) > v.at(i + 1) * (2 + i))
            {
                weight = v.at(i);
            }
            else
            {
                weight = v.at(i + 1) * (2 + i);
            }
 
            if (weight > maxWeight)
                maxWeight = weight;
        }
    }
    else
    {
        maxWeight = v.at(0);
    }
 
    cout << maxWeight << endl;
 
    return 0;
}

4307번 문제 : 개미

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> result;
 
int main()
{
    int cases;
    cin >> cases;
 
    for (int i = 0; i < cases; i++)
    {
        int length, numOfAnts;
        cin >> length >> numOfAnts;
 
        vector<int> v;
 
        for (int j = 0; j < numOfAnts; j++)
        {
            int startPosition;
            cin >> startPosition;
 
            if (startPosition <= length / 2)
            {
                v.push_back(startPosition);
            }
            else
            {
                v.push_back(length - startPosition);
            
            }
        }
        
        sort(v.begin(), v.end(), greater<int>());
        
        result.push_back(v.at(0));
        result.push_back(length - v.at(v.size() - 1));
    }
 
    for (int i = 0; i < result.size(); i++)
    {
        cout << result.at(i) << " ";
        if (i % 2 == 1)
            cout << endl;
    }
    
    
    return 0;
}

메모:

- 가장 늦은 시간을 구할때 개미가 충돌할 때 방향을 바꾸는 것이 그냥 지나치는 것과 결국 같다 -> 이 부분이 핵심