[백준] 2217 로프 with C++

문제설명

---

입출력 예제

---

개념

　각 로프는 고유한 중량 한계를 가지고 있으며 이를 초과할 수 없다. 이때 로프 2개가 각각 10kg, 15kg을 버틸 수 있다고 하면, 10kg 한 개를 쓸 땐 10kg, 15kg 한 개를 쓸 땐 15kg, 10kg과 15kg을 함께 쓰면 각 로프가 10kg씩 버틸 수 있으므로 20kg를 버틸 수 있다.

 

　이러한 특징에 착안하여 로프들을 강도에 따라 정렬하여 가장 강한 로프부터 시작하여 점점 약한 로프를 추가하며, 각 단계에서의 최대 중량을 계산할 수 있다. 이때 로프들 중 일부만을 선택해야 할 경우도 고려해야 한다. 

 

　예를 들어, 10, 20, 30, 40, 50kg을 버틸 수 있는 로프 5개가 있다고 가정해 보자. 

 

1. 50kg: 50kg

2. 50kg, 40kg: 40 + 40 = 80kg

3. 50kg, 40kg, 30kg: 30 + 30 + 30 = 90kg

4. 50kg, 40kg, 30kg, 20kg: 20 + 20 + 20 + 20 = 80kg

5. 50kg, 40kg, 30kg, 20kg, 10kg: 10 + 10 + 10 + 10 + 10 = 50kg

 

　즉, 단일 강도가 가장 높은 로프부터 시작하여 (최솟값 x 로프의 개수)를 계산하면 쉽게 해결할 수 있다.

---

풀이

#include <iostream>
#include <algorithm>

int main() 
{
    int N;
    std::cin >> N;
    
    int* ary = new int[N];
    
    for (int i = 0; i < N; ++i) 
   		std::cin >> ary[i];

　우선 로프의 개수 N개만큼 배열을 동적할당 해준 후, 로프의 한계 중량을 입력한다.

　

    std::sort(ary, ary + N, std::greater<int>());

    int result = 0;

    for (int i = 0; i < N; ++i) 
        result = std::max(result, ary[i] * (i + 1));
    
    std::cout << result;

    delete[] ary;
    return 0;
}

　배열을 내림차순으로 정렬한 후, 결괏값에 단일 한계 중량이 가장 높은 것부터, 병렬로 연결했을 때의 중량을 비교하며 최댓값을 result 변수에 할당한다. 그리고 그 결과를 출력하면 문제를 해결할 수 있다.

 

총합본

#include <iostream>
#include <algorithm>

int main() 
{
    int N;
    std::cin >> N;

    int* ary = new int[N];

    for (int i = 0; i < N; ++i) 
        std::cin >> ary[i];

    std::sort(ary, ary + N, std::greater<int>());

    int result = 0;

    for (int i = 0; i < N; ++i) 
        result = std::max(result, ary[i] * (i + 1));
    
    std::cout << result;

    delete[] ary;
    return 0;
}