[BOJ][실4][2217] 로프

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

로프가 견딜 수 있는 무게를 입력받고 정렬합니다.

arr[i] = i번째 로프가 견딜 수 있는 무게
arr[i] * (n-i) = i번째 로프부터 가장 단단한 로프까지 사용할 때 견딜 수 있는 무게(가장 약한 로프 * 갯수)

정답코드

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

using ll = long long;
using pii = pair<int, int>;

const int MAX = 100'001;

int arr[MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m, k;
map<int, int> mp;
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        ans = max(ans, arr[i] * (n - i));
    }
    cout << ans;
    return 0;
}

Success Notice: 수고하셨습니다.