로프 (feat. 백준, 2217번)

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

2217번: 로프

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, ans = 0, cnt = 0;
    priority_queue<int> q;
    cin >> N;
    for(register int n = 0, v; n < N; ++n)
        cin >> v, q.push(v);
    while(!q.empty()){
        ans = max(ans, q.top() * ++cnt);
        q.pop();
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

1. N=3, 로프의 길이가 10, 15, 12라고 가정했을때
   - 15 하나를 사용하는 경우 15 * 1 = 15
   - 15, 12 두개를 사용하고 최소값인 12 * 2 = 24
   - 15, 12, 10 세개를 사용하고 최소값인 10 * 3 = 30
   로 풀이할 수 있습니다. 사용하는 로프들 중 최소값 초과로 사용할 경우 로프가 끊어지기 때문입니다.
2. 따라서 위와 같은 경우, 정답은 30입니다.