문제
로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.
헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.
하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.
입력
첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1≤N≤10000)
둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t(1),t(2),⋯,t(N)가 주어진다. (0≤t(i)≤10^18)
출력
M의 최솟값을 출력한다.
예제 입력 1
5 1 2 3 4 5 |
예제 출력 1
5 |
PT 첫째 날에 1과 4를 선택하고, 둘째 날에 2와 3을 선택하고, 마지막 날에 5를 선택하면 M은 5가 되며, 이때가 M이 최소일 때이다.
Solution
#include<stdio.h>
#include<stdlib.h>
int compare(const void *x,const void *y)
{
return *(unsigned long long int *)x>*(unsigned long long int *)y?1:*(unsigned long long int *)x==*(unsigned long long int *)y?0:-1;
}
int main(void)
{
int N;
unsigned long long int *t=NULL, M=0;
scanf("%d", &N);
t=(unsigned long long int *)malloc(N*sizeof(unsigned long long int));
for(int i=0;i<N;i++)
scanf("%llu", &t[i]);
qsort((void *)t,(size_t)N,sizeof(unsigned long long int),compare);
if(N%2==1)
{
M=t[N-1];
for(int i=0;i<N/2;i++)
M=t[i]+t[N-i-2]>M?t[i]+t[N-i-2]:M;
}
else
for(int i=0;i<N/2;i++)
M=t[i]+t[N-i-1]>M?t[i]+t[N-i-1]:M;
printf("%llu\n", M);
free(t);
return 0;
}
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 20361번: 일우는 야바위꾼 (0) | 2020.12.21 |
---|---|
<백준 알고리즘> 20206번: 푸앙이가 길을 건너간 이유 (0) | 2020.12.16 |
<백준 알고리즘> 20299번: 3대 측정 (0) | 2020.12.15 |
<백준 알고리즘> 20205번: 교수님 그림이 깨지는데요? (0) | 2020.12.15 |
<백준 알고리즘> 20125번: 쿠키의 신체 측정 (0) | 2020.12.15 |