[c++] 백준 20300: 서강근육맨

[c++] 백준 20300: 서강근육맨

🥈실버 3

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

20300번: 서강근육맨

---

접근

N이 짝수일 때와 홀수일 때를 구분해서 코드를 작성해야 한다.

먼저, 입력받은 값을 내림차순으로 정렬시켜보자.

 

5 4 3 2 1

9개의 운동기구가 있는 경우에도 PT를 5번 받지만,
마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

N이 홀수인 경우에는, 가장 먼저 오는 운동기구는 반드시 하나만 사용해야 한다.

5를 따로 때놓고, 나머지 4 3 2 1의 경우에 대해서 생각해야 한다는 것이다.

 

4 3 2 1에서 2개씩 골랐을 때의 최솟값은 제일 왼쪽에 있는 값과 제일 오른쪽의 있는 값의 합이다.

따라서 5개의 값 중 1개 혹은 2개씩 골라 더한 값에서 최솟값을 구하려면

(5), (4, 1), (3, 2) -> 최솟값 = 5가 된다.

 

이 경우에는 모든 경우의 합이 5로 똑같이 나오게 되어 상관없지만, 다르게 나오게 되는 경우도 고려해야 한다.

 

만약 N이 5이고, 입력 값이 다음과 같다고 가정해보자.

 

8 7 5 4 2

 

이 경우에는 다음과 같이 묶을 수 있을 것이다.

(8), (7, 2), (5, 4)

각각의 합을 구하면 8, 9, 9가 된다.

 

근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다.

8, 9, 9중에서는 향빈이는 아무리 적어도 근손실 정도가 9를 넘지 않을 수 없다.

결국, 이렇게 더해진 값들 중에서 최댓값을 구해서 출력해야 한다.

 

 

짝수의 경우에도 마찬가지이다.

다만, 두 개씩 짝이 맞기 때문에 따로 하나를 뺄 필요가 없다.

 

똑같이 내림차순으로 정렬하고,

가장 왼쪽에 있는 값과 가장 오른쪽에 있는 값을 더한다.

N = 6

8 5 4 4 2 1

위와 같은 값이 주어졌을 경우,

(8, 1), (5, 2), (4, 4)와 같이 고르는 값이 합의 최소가 될 것이다.

각 값을 서로 더하면 9, 7, 8이 될 것이고, 여기서 최댓값인 9가 출력되어야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  ll arr[N];
  for (int i = 0; i < N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N, greater<>());
  vector<ll> vec;
  ll ans = 0;

  if (N % 2 != 0) {
    vec.push_back(arr[0]);

    for (int i = 1; i <= N/2; i++) {	// 첫번째 값을 제외하고 맨 왼쪽과 맨 오른쪽 값을 더한다.
      vec.push_back(arr[i] + arr[N-i]);
    }
  }
  else {
    for (int i = 0; i < N/2; i++) {	// 첫번째 값을 포함한 채로 맨 왼쪽과 맨 오른쪽 값을 더한다.
      vec.push_back(arr[i] + arr[N-i-1]);
    }
  }
  ans = vec[0];
  for (auto a: vec){
    ans = max(ans, a);
  }
  cout << ans;
  return 0;
  
}