(C++) - 백준(BOJ) 2217번 : 로프

www.acmicpc.net/problem/2217

2217번: 로프

greedy문제였습니다.

 

풀이방법

 1. 귀류법으로 greedy로 푸는 것이 합당한지 검증합니다. 귀류법이란 세운 명제에 반하는 명제를 세운 후 해당 명제가 거짓임을 보여 결론적으로 기존 명제가 참임을 증명하는 방법입니다. 먼저 가정을 세웁니다.

가정 : 들어올릴 수 있는 중량이 최대인 로프를 선택하면 최대 중량을 들어올릴 수 있다.

반하는 가정 : 들어올릴 수 있는 중량이 최소인 로프를 선택하면 최대 중량을 들어올릴 수 있다.

반하는 가정이 거짓입니다. 예시로 설명하자면 15인 로프를 선택할 때 최대 중량은 15 10인 로프를 선택할 때 최대 중량은 10이기 때문입니다. 따라서 처음 세운 가정이 참임을 도출할 수 있고 greedy문제라는 것을 알 수 있습니다.

 

 2. 식을 세웁니다.

 오름차순으로 정렬한 후 가장 입력받은 로프중량 배열의 마지막 원소부터 확인하면서 다음의 공식을 따라갑니다.

 answer = max(answer, ropeWeightp[n-i-1]*(i+1);

최대인 중량들을 선택하면서 중량을 계산합니다. n-i-1번째 로프를 선택했다는 말은 이전에 n-1부터 해당 로프까지 선택했다는 말이므로 i+1을 곱했을 때 해당 로프들이 버틸 수 있는 중량을 의미합니다.

 

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, ans;
int main(){
    cin >> n;
    vector <int> ropeWeight(n);
    for(int i = 0; i < n; i++){
        cin >> ropeWeight[i];
    }
    sort(ropeWeight.begin(),ropeWeight.end());
    for(int i = 0; i < ropeWeight.size(); i++){
        ans = max(ans,ropeWeight[n-i-1]*(i+1));
    }
    cout << ans <<'\n';
}