BOJ 2217, 로프
ProblemSolving ·이 문제는 그리디 문제입니다. 수학이나 물리학과도 연관이 있지만 모르셔도 상관 없을 것 같습니다.
풀이
줄이 1개라면 그 줄이 버틸 수 있는 만큼의 무게만 들 수 있고
줄이 2개라면 가장 약한 줄이 가능한 무게의 2배만큼 들 수 있고
줄이 3개라면 가장 약한 줄이 가능한 무게의 3배만큼 들 수 있겠죠?
줄을 무게순으로 정렬해주고 가장 무거운 줄부터 시작해서 한개씩 줄을 추가하면서
무게를 비교하면 최댓값을 구할 수 있겠죠?
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n, arr[100001], Max;
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)
scanf("%d", &arr[i]);
sort(arr, arr + n);
for (int i = n - 1; i >= 0; i--)
{
int com = arr[i] * (n - i);
if (com > Max)
Max = com;
}
printf("%d", Max);
return 0;
}