[백준/C++] 2217번 로프

1.문제 링크

2217

2. 풀이 전 계획과 생각

• 그리디 알고리즘으로 풀기

3. 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int compare(int i, int j){
    if(i>j) return true;
    return false;
}

int main(){
    int n; cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    // 내림차순 정렬
    sort(v.begin(), v.end(), compare);
    
    int max = v[0];
    for(int i=1;i<=n;i++){
        if(max<(i*v[i-1])) max=i*v[i-1];
    }
    
    cout<<max;
}

1. 입력 배열 내림차순 정렬

2. k개의 로프를 사용해 중량이 w인 물체를 들어올릴 때 각각의 로프에 모두 고르게 w/k만큼 중량이 걸리게 되므로, for문을 돌리면서 max값을 찾는다.

4. 풀이하면서 고민했던 점

• 문제푸는 아이디어를 생각하는데 고민함.

5. 문제를 풀고 알게된 개념 및 소감

• 그리디 알고리즘에 대한 이해도가 올라감.