Algorithm

[BOJ] 서강근육맨 20300번 C++

따봉치치 2024. 4. 25. 18:13

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 𝑁개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 𝑀을 넘지 않도록 하고 싶다. 이때, 𝑀의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 𝑁이 주어진다. (1≤𝑁≤10000)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 𝑡1,𝑡2,⋯,𝑡𝑁가 주어진다. (0≤𝑡𝑖≤)

 

출력

 𝑀의 최솟값을 출력한다.

 

접근 방식

 

굉장히 간단한 문제다

PT를 최대 2번씩 받을 수 있으므로 정렬을 한 후에 최소값과 최댓값을 더하는 식으로 구하면 된다

즉, 

1 6 9 3 5 가 입력으로 들어온다면

1 3 5 6 9로 정렬하고

가장 끝에있는 값들끼리 더하면된다

 

하지만, 여기서 N이 짝수인지 홀수인지 나눠서 처리해 주어야 한다

왜냐면 홀수라면 무조건 PT 한번은 운동기구 1개만 사용할 수 있기 때문이다

그렇기 때문에 홀수라면 가장 최댓값을 빼고

(1,6) , (3,5)를 더해주면 된다

따라서 이 때의 M의 최솟값은 9가 된다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    vector<long long> v(N);
    for(int i=0; i<N; i++) cin>>v[i];
    sort(v.begin(), v.end());

    int st = 0, en;
    long long mx=0;
    if(N%2 == 0) en = N-1;
    else {
        en = N-2;
        mx = v[N-1];

    }

    while(st < en) {
        mx = max(v[st] + v[en], mx);
        st++;
        en--;
    }

    cout<<mx;
}