백준 2217 로프(greedy approach)

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

2217번: 로프

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 100000;
int N;
int arr[MAX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    int maxNum = 0;
    for (int i = 0; i < N; i++)
    {
        if (maxNum < arr[i] * (N - i))
            maxNum = arr[i] * (N - i);
    }
    cout << maxNum;
}

 

예를 들어 [1, 5, 10, 25, 50, 100]  N=6 이라는 배열이 주어졌다 가정해보자.

 

각 로프들이 들어야 하는 중량을 1이라 한다면 6개 모두가 가능하기 때문에 1*6=6이 될 것이다.

 

각 로프들이 들어야 하는 중량을 5라 한다면 1을 제외한 5개가 가능하기 때문에 5*5=25가 될 것이다.

 

↓

각 로프들이 들어야 하는 중량으 100이라 한다면 1개 만이 가능하기 때문에 100*1=100이 될 것이다.

 

즉, 결과값으로 나온 [6. 25, ... , 100] 중 최대값이 정답이 된다.