[C/C++] 백준 #2217 로프(탐욕 알고리즘)

#2217 문제는 정렬을 사용한 탐욕 알고리즘으로 풀 수 있는 문제입니다.

 

문제의 링크입니다.

https://www.acmicpc.net/problem/2217

2217번: 로프

 

n개의 로프가 있는데, 여러줄을 사용하면, 들어올리고자 하는 물건의 무게를 똑같이 분담하면서 물건을 올릴 수가 있습니다.  로프마다 견딜 수 있는 하중이 따로 있어서, 현재 가지고 있는 로프로 가능한 무거운 물건을 올리고자 할 때, 그 무게가 얼마인가입니다.

 

 

예를 들어서 무게를 3, 7, 6, 4 견딜 수 있는 로프가 있다고 해보죠.

로프를 1개씩만 쓰면, 최대 무게는 7입니다.

로프를 2개씩만 쓰면, 최대 무게는 12이 되겠죠.

로프를 3개씩만 쓰면, 최대무게는 12가 되겠죠.

로프를 4개씩만 쓰면, 최대무게는 12가 되겠죠.

 

위의 값은 사실 2개 이상 쓰면 최대 무게는 변하지는 않습니다.

이렇게 머리속에서 한번 구상을 해보면 어떻게 문제를 풀지 알 수 있습니다.  k개를 쓸때는 탐욕적으로 k개의 상위 로프를 이용해서 가장 작은 값에 k를 곱하면 되겠죠.  여기서 정렬이 필요하다는 것을 알 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2217
//        - by Aubrey Choi
//        - created at 2019-09-17
//------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, v[100000], max=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",v+i);
    std::sort(v,v+n);
    for(int i=0;i<n;i++) max=(max<(n-i)*v[i])?(n-i)*v[i]:max;
    printf("%d\n", max);
}