[C++] 백준 온라인 저지 2217번 로프 풀이

각각 견딜 수 있는 중량이 다른 로프들을 이용해서 들 수 있는 최대 무게를 구하는 문제

 

---

문제의 조건

 

1. N개의 밧줄이 주어진다. 

 

2. 이 밧줄들은 각각 동일한 무게로 나눠서 한 물체를 들게 된다. 

100kg 짜리 물체를 4개의 밧줄로 나눠 든다면 25kg씩 나눠 든다. 

 

3. 모든 밧줄을 사용하지 않아도 되고 가장 많은 무게를 들 수 있는 밧줄 몇 개만 골라서 써도 된다. 

 

4. 주어진 밧줄들을 이용해서 가장 많이 들 수 있는 무게를 출력하기 

 

---

풀이 과정

 

처음에는 단순하게 밧줄 중 최솟값을 구해서 모든 밧줄의 갯수만큼 곱하면 되겠다고 생각했습니다. 

하지만 실패 ㅠ.ㅠ

 

그러고 다시 생각해 보니까 1kg 짜리만 5개 있다가 100kg 짜리 하나 있으면 100kg 짜리 하나만 썼을 때 가장 많이 들 수 있으니까

밧줄의 무게가 적은 것부터 하나씩 제외 해가면서 들 수 있는 무게를 구해야 겠다는 생각이 들었습니다. 

 

그래서 처음에는 정렬되지 않은 배열에서 min_element 함수로 최솟값을 구한 다음에 현재 가능한 최대 중량을 구하고

erase 함수로 min_element 원소를 삭제하면서 밧줄 배열이 빌 때까지 반복하는 방식으로 짰는데 (네 효율적이지 않았던거 압니다...)

erase 연산에서 오래 걸려서 그런지 시간 초과가 나서 배열 인덱스를 이용하는 방식으로 다시 짜서 통과했습니다. 

 

정리

1. 밧줄 배열을 오름차순으로 정렬한다. 

 

2. 0번째 인덱스부터 탐색하면서 해당 인덱스의 밧줄 무게와 (밧줄 배열 길이 - i) 값을 곱한 값을 구해서 최대값을 구한다. 

 

---

위의 과정을 코드로 옮기면 아래와 같습니다. 

 

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

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> ropes;
    for (int i = 0; N > i; i++)
    {
        int n;
        cin >> n;
        ropes.emplace_back(n);
    }
    
    //중량이 적은 것부터 오름차순 정렬 
    sort(ropes.begin(), ropes.end());
    
    int answer = 0;
    for (int i = 0; ropes.size() > i; i++)
    {
        //인덱스를 0번부터 증가시키면서 전체 밧줄 갯수에서 인덱스 번호만큼 빼면
        //밧줄을 하나씩 제외시키면서 남은 밧줄들의 갯수를 구할 수 있다. 
        //현재 인덱스의 중량과 남은 밧줄들의 갯수를 곱한 값을 이전 최대값과 비교한다. 
        int minRope = ropes[i];
        int maxLoad = static_cast<int>(minRope * (ropes.size() - i));
        answer = max(answer, maxLoad);
    }
    
    cout << answer;
    
    return 0;
}