백준 2217번: 로프 C++코드(정렬, 그리디 알고리즘)

 

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int n;
    int temp;
    int rope[100001];
    int min = 0;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &rope[i]);
    }
    sort(rope, rope+n);
    for(int i=0; i<n; i++){
        if(rope[i]*(n-i) > min){
            min = rope[i]*(n-i);
        }
    }
    printf("%d", min);
}

설명

n 개의 로프의 정보를 입력 받은 뒤 이를 배열에 넣고 정렬해준다. 그리고 정렬된 배열의 앞 인덱스부터 rope[0]*(n), rope[1]*(n-1)... 이런 식으로 계속 반복문을 돌려서 이 중 가장 큰 값을 출력해준다. 이렇게 해야하는 이유는 임의의 로프는 제외해도 되기 때문에, 만약에 로프가 5개가 있는데, 버틸 수 있는 힘이 각각 10, 8, 8, 8, 3 이라면 3을 넣고 무게를 달면 15가 최대이지만, 3을 제외시키면, 32까지 무게를 달 수 있기 때문이다.

 

문제점

처음 문제를 풀 때, 모든 로프를 사용해야하는 줄 알고 풀었다가 틀린 후 문제를 다시 읽어보았다.