2217. 로프

그리디 문제이다.

 

---

1. 문제 풀이

2. Solution

---

1. 문제 풀이

필자는 로프 문제를 그리디로 해결했다.

필자가 생각해 낸 로프 문제의 탐욕법은 "정렬을 통해 k를 계산 + 각 로프당 들 수 있는 최소 중량을 이용하자" 이다.

 

예제 문제를 보면, 2개의 로프에 대해 각각 20, 25의 중량을 들 수 있다.

-1개의 로프를 포함하는 경우: 최대 25 중량 가능

-2개의 로프를 포함하는 경우: 최대 40 중량 가능

단, 각 로프당 들 수 있는 최소 중량 = w/k (40중량/2개 = 20중량)을 만족해야 한다.

 

그렇기 때문에, 필자는 로프 문제를 해결하기 위해

1) 우선 로프가 들 수 있는 무게를 정렬 (오름차순 정렬)

   * 이때, 정렬을 안 하면, rope[i] <= rope[i + 1] 을 보장할 수 없다.

   * rope[i] <= rope[i + 1] 을 보장해야, k의 개수를 알 수 있다.

 

2) 가장 무거운 중량을 들 수 있는 로프 rope[N - 1] 부터 해당 로프가 포함될 경우 들 수 있는 최대 중량(w) 계산

   * 이때, 각 로프당 들 수 있는 최소 중량 = w/k 를 고려해야 하기 때문에, i번째 로프가 들 수 있는 무게 rope[i] * 사용할 로프수(k)

 

 

2. Solution

// baekjoon 2217 로프

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int N, vector<int>& rope)
{
    sort(rope.begin(), rope.end());


    int MAX = 0;
    int w, k;

    for(int i = N - 1; i > -1; i--)
    {
        k = N - i;
        w = rope[i] * k;

        MAX = (w > MAX) ? w : MAX;
    }

    return MAX;
}


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

    vector<int> rope(N);
    for(int i = 0; i < N; i++) cin >> rope[i];

    cout << solution(N, rope) << endl;
    
    return 0;
}