C - [백준 2217] 로프 (feat. 그리디, 퀵 정렬)

2025.02.02 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

[자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

 

 

 

 

로프 (백준 2217번) 문제 풀이

문제 설명

여러 개의 로프가 주어졌을 때, 각 로프는 각자 버틸 수 있는 최대 중량이 정해져 있습니다. 여러 로프를 병렬로 연결하여 물체를 들어 올릴 때, 병렬 연결된 로프들은 각 로프가 버틸 수 있는 중량을 공유합니다. 이때, 들어 올릴 수 있는 최대 중량을 구하는 문제입니다.

문제 링크: 백준 2217번 로프

---

Checkpoint

이 문제는 그리디 알고리즘을 통해 해결할 수 있습니다. 가장 많이 무게를 버틸 수 있는 경우를 계산하기 위해 다음과 같은 접근 방식을 사용합니다:

1. 각 로프가 버틸 수 있는 중량을 오름차순으로 정렬합니다.
2. 가장 작은 로프부터 병렬로 연결하는 상황을 가정하여 각 로프가 감당할 수 있는 최대 중량을 계산합니다.
3. 각 로프가 감당할 수 있는 중량은 로프 중량 × 사용된 로프의 수로 구할 수 있습니다.
4. 모든 경우 중 가장 큰 값을 선택합니다.

포인트는 그리드의 최적해를 구하기 위해서 어떻게 수를 정렬할 것인가에 대해 고민을 해야한다는 것입니다.

해당 문제는 비교적 직관적인 편에 속하나, 이에 대해 인지를 하게 되었으며 다른 문제들을 통해 이것에 대한 능력을 키워볼까합니다.

---

구현 알고리즘

1. 로프의 중량을 입력받고 정렬합니다.
2. 각 로프에 대해 최대 중량을 계산합니다.
3. 최대 중량 값을 비교하여 최종 결과를 출력합니다.

---

코드 구현

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

// 비교 함수 (qsort에 사용)
int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);  // 내림차순 정렬
}

int main() {
    int N;
    int ropes[100000];  // 최대 100,000개의 로프

    // 로프 개수 입력
    scanf("%d", &N);

    // 각 로프가 버틸 수 있는 최대 중량 입력
    for (int i = 0; i < N; i++) {
        scanf("%d", &ropes[i]);
    }

    // 로프의 중량을 내림차순으로 정렬
    qsort(ropes, N, sizeof(int), compare);

    int max_weight = 0;

    // 각 로프를 사용할 때 들어 올릴 수 있는 최대 중량 계산
    for (int i = 0; i < N; i++) {
        int weight = ropes[i] * (i + 1);  // 현재 로프가 감당할 수 있는 중량
        if (weight > max_weight) {
            max_weight = weight;  // 최대 중량 갱신
        }
    }

    // 결과 출력
    printf("%d\n", max_weight);

    return 0;
}

---

코드 설명

1. 입력 처리 및 정렬
   N개의 로프 정보를 입력받고, qsort를 사용하여 내림차순으로 정렬합니다.
   • 큰 중량을 버틸 수 있는 로프가 앞쪽에 오도록 정렬합니다.
2. 최대 중량 계산
   각 로프가 감당할 수 있는 최대 중량을 ropes[i] * (i + 1)로 계산합니다.
   • 여기서 (i + 1)은 현재까지 사용한 로프의 수를 의미합니다.
   • 반복문을 통해 최대 중량을 갱신합니다.
3. 결과 출력
   최종적으로 구한 최대 중량 값을 출력합니다.

---

예제 입력과 출력

입력 예시

2
10
15

출력 예시

20

설명:

• 15kg 로프 하나만 사용할 경우: 15kg 가능
• 두 로프를 병렬로 사용할 경우: 10kg × 2 = 20kg 가능
  따라서 최대 중량은 20kg입니다.

---

핵심 정리

• 이 문제는 큰 중량을 버틸 수 있는 로프부터 사용하여 그리디 방식으로 해결할 수 있습니다.
• 시간 복잡도는 정렬 과정에서 O(N log N)이 소요됩니다.
• 병렬 연결 시 각 로프가 감당할 수 있는 중량을 적절히 계산하는 것이 중요합니다.

---