백준 20300번 [서강근육맨](C++) -yes6686- 티스토리

백준 문제 풀이: 20300 [서강근육맨]

---

문제 링크: https://www.acmicpc.net/problem/20300

문제 설명:

운동 기구를 짝지어 한 번에 운동을 수행할 때, 가장 큰 부담이 되는 짝의 합을 최소화하려고 합니다. 운동 기구의 개수 n과 각각의 기구가 주어졌을 때, 최적의 짝짓기로 최소화된 최대 운동 기구의 합을 구하는 문제입니다.

---

문제 해결 코드

// 백준 20300 - 서강근육맨
#include <iostream>
#include <algorithm>
using namespace std;

long long arr[10001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 운동 기구를 오름차순으로 정렬
    sort(arr, arr + n);

    long long maxWork = 0;

    if (n % 2 == 0) {
        // 짝수 개: 짝을 지어 합을 계산
        for (int i = 0; i < n / 2; i++) {
            maxWork = max(maxWork, arr[i] + arr[n - i - 1]);
        }
    } else {
        // 홀수 개: 하나를 혼자 사용하고 나머지를 짝지어 합 계산
        maxWork = arr[n - 1];
        for (int i = 0; i < (n - 1) / 2; i++) {
            maxWork = max(maxWork, arr[i] + arr[n - i - 2]);
        }
    }

    cout << maxWork << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 운동 기구의 부담이 최소가 되도록 하기 위해, 운동 기구를 정렬합니다.
  • 가장 작은 기구와 가장 큰 기구를 짝지어 합이 최소화되도록 계산합니다.
• 구현 세부사항:
  • 기구의 개수가 짝수인 경우, 모든 기구를 짝지어 계산합니다.
  • 기구의 개수가 홀수인 경우, 가장 큰 기구는 혼자 사용하고 나머지 기구를 짝지어 계산합니다.
• 시간 복잡도 분석:
  • 정렬: O(n log n)
  • 최대값 계산: O(n / 2)
  • 총 시간 복잡도: O(n log n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!