문보고등학교에서 프로그래밍을 가르치고 있는 Yulo.K 선생님은 요즘 고민이 생겼다. 공부를 잘하는 학생들은 점점 더 점수가 올라가고, 공부를 못하는 학생들은 점점 더 점수가 내려가서, 공부를 못하는 학생들이 점점 공부를 포기하고 있는 것이다. 어떻게 하면 이 문제를 해결할 수 있을까 고민하던 Yulo.K 선생님은 여러 책, 기사를 찾아보고 아래와 같은 새로운 채점 방식을 제안했다.
"다음 시험에는 모든 학생들을 두 명씩 짝을 지어서 두 학생의 평균 점수로 두 학생의 점수를 매길 거다. 내가 두 명씩 짝을 지어줄 테니까 서로 도와주면서 열심히 공부하길 바란다. 아, 그리고 만약에 전체 학생 수가 홀수면 한 명 남는 학생은 그냥 자기 점수를 그대로 받을 거다."
Yulo.K 선생님은 짝을 지어준 후 각 학생들의 기대 점수 중에 1등의 점수를 제일 작도록 하고 싶다. 기대 점수는 짝지어준 두 학생의 지난 시험 점수의 평균으로 한다. 학생 N명의 지난 시험 점수가 주어질 때, Yulo.K 선생님의 계획대로 짝을 지으면 1등의 기대 점수가 몇 점이 되는지 구하라.
입력
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. ( T ≤ 50 )
각 테스트 케이스의 첫 번째 줄에는 자연수 N이 주어진다. ( 3 ≤ N ≤ 40 )
두 번째 줄에는 학생들의 지난 시험 점수를 나타내는 N개의 숫자가 입력된다.
시험 점수는 0점 이상 100점 이하의 정수다.
출력
각 테스트 케이스에 대해 한 줄에 1등의 기대 점수를 소수점 첫 번째 자리까지 출력한다.
예제 입력
3
3
48 96 73
4
0 0 98 99
5
35 85 94 76 40
예제 출력
73.0
49.5
76.0
생각해야 할 점
어떻게 짝을 지어야 하는가.
우리의 주된 목적은 짝을 지어서 최대한 모든 수를 다 작게 만드는 것입니다.
그렇게 하기 위해서는 작은 수와 큰 수를 짝을 지어 기대값을 낮춰야합니다.
그렇기 때문에 가장 작은 수는 가장 큰 수와 짝을 짓고
그 다음으로 작은 수는 그 다음으로 큰 수와 짝을 지어야 합니다.
소스 코드 확인
초기 설정
sort(&Data[1], &Data[N+1]);
max=0;
큰 수와 작은 수를 쉽게 짝을 짓기 위해서 데이터를 정렬해줍니다.
C++의 algorithm 헤더파일의 sort를 사용하였습니다.
해결 부분
for(int i=1; i<=N/2; i++)
if(max < Data[i] +Data[N-i+1]) max = Data[i] + Data[N-i+1];
if(N%2)
if(max < Data[N/2+1] * 2) max = Data[N/2+1] * 2;
printf("%0.1f\n", max / 2);
전체 개수의 반만큼 나누어 앞에 부분과 뒷 부분을 더해줍니다.
(앞에 부분은 작은 수, 뒤에 부분은 큰 수가 되겠습니다.)
그리고 홀수라면 가운데 수는 평균값을 구하지 않기 때문에
2배를 곱해서 저장합니다.
(값이 하나이기 때문에 2개가 있듯이 2배를 해줘야합니다.)
#include <iostream>
using namespace std;
#include <algorithm>
void YULO();
int main()
{
int T;
scanf("%d", &T);
while(T >= 1)
{
--T;
YULO();
}
return 0;
}
void YULO()
{
int Data[50], N;
double max;
scanf("%d", &N);
for(int i = 1; i<=N; i++)
scanf("%d", &Data[i]);
sort(&Data[1], &Data[N+1]);
max=0;
for(int i=1; i<=N/2; i++)
if(max < Data[i] +Data[N-i+1]) max = Data[i] + Data[N-i+1];
