[BaekJoon 2217번] 로프(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

2217번: 로프

 

 

[문제 설명]

 

 

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

 

[입력]

 

 

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

 

[출력]

 

 

첫째 줄에 답을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
2 10 15	20

 

 

[문제 풀이]

 

 

주요 조건

1. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸린다.

2. 모든 로프를 사용해야할 필요가 없다. 임의로 몇개의 로프를 골라서 사용해도 된다.

 

예시를 들어 보도록 하겠다.

입출력 예제에서 2개의 로프를 더 추가한 예제이다

{10, 15, 7, 4} 로프들이 있다.

여기서 들어올릴 수 있는 물체의 최대 중량을 구해내려면 어떻게 할까?

 

➔ 가장 무거운 무게를 들어올리는 로프가 우선이다.

그래서 내림 차순으로 정렬한다.

내림 차순으로 정렬하게 되면 {15, 10, 7, 4}로 정렬이 된다.

 

15 로프를 가지고 들어올릴 수 있는 물체의 최대 중량은 15이다.

15와 10 로프를 사용한다면 들어올릴 수 있는 물체의 최대 중량은 20이다.

15와 10, 7 로프를 사용한다면 들어올릴 수 있는 물체의 최대 중량은 21이다.

15와 10, 7, 4 로프를 사용한다면 들어올릴 수 있는 물체의 최대 중량은 16이다.

➔ 15, 10, 7 로프를 사용하여 물체의 최대 중량 21을 버티고,

각각 서로 7씩 무게를 부담하기 때문에 끊어지지 않고 버틸 수 있다.

 

위 예시로 봤을 때 들어올릴 수 있는 물체의 최대 중량은

들어올릴 수 있는 최대 무게 = (로프를 사용하는 횟수 *  사용하는 로프 중 작은 값) 으로 알 수 있다.

 

그래서 위 내용을 바탕으로 아래의 코드를 작성했다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

vector<int> info;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    info.resize(N, 0);
    for(int i = 0; i < N; ++i) {
        int weight; cin >> weight;
        info[i] = weight;
    }
    sort(info.begin(), info.end(), greater<int>()); 
    int result = 0;

    int select = 1;
    for(int i = 0; i < N; ++i) {
        result = max(result, info[i] * select);
        select += 1;
    }
    cout << result;
}