문제

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

코드

n=int(input())
nums=[]
for i in range(n):
    nums.append(int(input()))

nums.sort()

max=-1
for i in range(1,n-1):
    avg_min=nums[i]+nums[0]+nums[i+1]
    avg_max=nums[i-1]+nums[i]+nums[n-1]
    if abs(avg_min-nums[i]*3)>max:
        max=abs(avg_min-nums[i]*3)

    if abs(avg_max-nums[i]*3)>max:
        max=abs(avg_max-nums[i]*3)


print(max)

그리디 답지않은 문제라고 생각했다... 조합을 통해서 경우의 수를 구하고 그를 바탕으로 탐색하고자 했으나 메모리 초과로 실패했다.

그리디 문제는 일단 모르겠으면 정렬을 하자

평균과 가운데 값이 가장 큰차이가날려면

가장 큰 평균 - 가운데 값 or 가장 작은 평균 - 가운데 값 둘중 하나이다.

정렬을 진행하고 맨 끝 맨 뒤를 제외한 값들은 가운데 값이 될 기회가 있는 수들이다. 즉 1 ~ n-2까지의 인자를 탐색하여서

가장 작은 세수 합은 a[0]+a[i]+a[i+1]

가장 큰 세수 합은 a[i-1]+a[i]+a[n-1]

이두개만 확인하며 탐색한다.