[백준알고리즘] 2217번: 로프 -C

[백준알고리즘] 2217번: 로프 -C

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

2217번: 로프

 

Greedy Algorithm이 DP보다는 역시 생각하기가 쉬운 것 같다.

 

 

일단 위 문제를 풀기 위해서는 최대 weight를 구하는 방법을 생각해봐야 한다. 각 rope는 각각 버틸 수 있는 중량이 있다. 모든 로프를 반드시 선택할 필요 없이 들 수 있는 가장 무거운 무게를 구해야 하기 때문에 여러 줄이 있을 때 그 줄에서 가장 버틸 수 있는 중량이 작은 로프를 기준으로 삼아야한다.

 

예를 들어서 설명해보겠다. 3개의 로프가 각각 쓰인 만큼의 무게를 버틸 수 있다고 생각해보자.

 

rope1 = 16

rope2 = 40

rope3 = 10

 

각각의 로프의 한계만큼 무게를 들게 될 경우를 살펴보도록 하자. rope1의 한계만큼 들 경우에는 rope2도 16의 무게를 들 수 있기 때문에 16의 무게를 총 2개의 줄이 들 수 있다. 이때의 물건의 무게는 32가 된다.

rope2가 물건을 들 경우에는 40의 무게를 들 수 있다. 하지만 다른 줄들은 40의 무게를 들지 못하고 rope2만 들게 된다. 이때 물건의 무게는 40이 된다.

rope3이 들 때의 경우에는 10의 무게를 들 수 있다. 이때 rope1과 rope2도 10의 무게를 들 수 있게 된다. 이때 물건의 무게는 30이 된다.

 

위의 3가지 경우가 각각의 줄의 한계만큼 들 때의 한계이다.

저 중에서 rope2가 혼자 들 때가 weight의 최대 무게가 된다.

 

 

이런 아이디어를 가지고 문제를 풀 것이기 때문에 일단 로프가 들 수 있는 무게의 내림차순으로 정렬을 해줄 것이다. 그리고 rope를 하나씩 추가해가면서 "(추가된 rope가 들 수 있는 무게) * (현재까지의 로프의 수)"를 계산해 가면서 maximum을 계산하면 된다. "(추가된 rope가 들 수 있는 무게) * (현재까지의 로프의 수)" 이 식이 만족할 수 있는 이유는 rope가 버틸 수 있는 무게의 내림차순으로 정렬했기 때문에 추가되기 이전의 로프들은 추가된 로프가 들 수 있는 무게는 당연히 들 수 있기 때문이다.

 

코드는 다음과 같다. qsort() 함수를 사용해서 로프를 내림차순으로 정렬할 때 퀵 정렬을 했다.

 

#include <stdio.h>
#include <stdlib.h>

/* descending order */
int compare (const void* first, const void* second){
    if (*(int*)first > *(int*)second)
        return -1;
    else if (*(int*)first < *(int*)second)
        return 1;
    else
        return 0;
}

int main(void){
    int N, i, weight;
    int *rope;

    scanf("%d", &N);
        
    rope = (int *)malloc(sizeof(int) * N);
    for(i = 0; i < N; i++){
        scanf("%d", &rope[i]);
    }

    qsort(rope, N, sizeof(int), compare);

    weight = 0;
    for(i = 0; i < N; i++){
        weight = weight > rope[i] * (i + 1) ? weight : rope[i] * (i + 1);
    }

    printf("%d\n", weight);


    free(rope);
    return 0;
}

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다