BOJ 2217번: 로프

문제 설명

로프들에 대한 정보가 주어졌을 때, 들어올릴 수 있는 물질의 최대 무게 구하기
(병렬 연결로 물체 무게 나눌 수 있음)

🔗 문제 링크

핵심 아이디어

• 오름차순 로프 정렬
• 1 ~ n개의 로프 골랐을 때 각각 (i개 로프 중 가장 약한 애 * i)를 하여 최대 무게 갱신

코드

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

int n;
int w[100005];
int ans = 0;

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];
    
    sort(w, w + n); 

    for(int i = 1; i <= n; i++){
        ans = max(w[n-i] * i, ans);
    }

    cout << ans;
}

‼️ 놓친 부분

• 입력 값 범위 체크
• w배열을 오름차순 정렬 후 w[n - i]는 i개 로프 중 가장 약한 애
• 1-based vs 0-based index 헷갈림

**바킹독님 자료 참고: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/2217.cpp