[그리디/백준] 2405번 : 세 수, 두 M

- 문제 : https://www.acmicpc.net/problem/2405

 

문제 이해 

- 주어진 수들 중에서 세 개의 숫자를 구해 거기서 3 * (중위값 - 평균)의 최대값을 구한다. 

 

직관적으로 이해하기로는 중위값과 평균의 차이가 커야하므로 중위값은 최솟값과 비슷한 숫자여야하고 평균이 커야 하므로 배열의 최댓값이 무조건 들어가야 한다고 생각했다. 따라서 (0, 1, -1) 또는 (0, -2, -1) 두 개의 집단만 비교하면 된다고 생각해 진행했는데 21%에서 틀렸다. 

 

강의를 들어보니 중위값은 배열 전체의 값이 후보가 될 수 있고, 중위값을 기준으로 (중위값 - 최소 평균)과 (중위값 - 최대 평균) 중 최대값들을 누적해 가는 거라고 했다. 고려해야하는 케이스가 두 가지인 이유는 두 값의 절댓값을 계산하기 때문이다. 절댓값은 결국 두 값의 수직선 상에서의 거리이므로 중위값에서 최소의 값을 빼는 게 클 수도 또는 최대 평균에서 중위값을 빼는 게 클 수도 있다. 

 

풀이 로직

- 숫자들을 numbers에 저장한 뒤 오름차순 정렬한다.

- numbers의 원소들을 선형 탐색하면서 i번째 원소를 중위값으로 설정한 뒤 max_avg, min_avg를 구한다. 

- max_avg를 구하는 방법은 i번째 원소보다 작은 원소 중에 가장 큰 (i - 1) 원소와 배열 최대값인 (-1) 원소를 합해서 3으로 나누면 된다.

- min_avg를 구하는 방법은 i번째 원소보다 큰 원소중에 가장 작은 (i + 1) 원소와 배열 최소값인 (0) 원소를 합해서 3으로 나누면 된다.

- 각 중위값에서 최대값을 answer에 누적했다가 또 거기에서 최대값을 출력하면 정답이다. 

 

정답 풀이

import sys
input = sys.stdin.readline

n = int(input())

numbers = []
for _ in range(n):
    numbers.append(int(input()))

answer = []
numbers.sort()
for i in range(1, n - 1):
    median = numbers[i]
    max_avg = numbers[i - 1] + median + numbers[-1]
    min_avg = numbers[0] + median + numbers[i + 1]
    answer.append(max(abs(max_avg - 3 * median), abs(min_avg - 3 * median)))
    
print(max(answer))