백준 2405 자바 - 세 수, 두 M (BOJ 2405 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2405.java

 

 

1. a<b<c 라고 할 때, 중위값과 평균값의 차이의 세 배 값은 결국 다음을 뜻한다.

| ((a+b+c)/3 - b) * 3 | = | a+b+c-3b | = | a-2b+c |

따라서 차이를 크게 하려면 결국 a와 c를 고른 후, b는 최대한 작게고르거나, 크게골라야 한다.

즉, 중위값을 최대한 a와 가깝게 혹은 c와 가깝게 둬야 한다.

무슨말이냐면, 1 2 3 4 5 에서 a=1, c=5를 골랐다. 이 때 b는 2 또는 4 중에 골라야 한다.

 

2. 그래서 처음엔 정렬한 후 단순하게 a = 가장 작은 수(arr[0]), c = 가장 큰 수(arr[n-1]), b = max(arr[1], arr[n-2]) 라고 생각했는데, 애초에 | a-2b+c |를 크게하는 것만이 목적이기 때문에 사실 모든 경우를 다 봐야 한다. 즉 b를 고르는 방식은 '1'임이 확실하지만, a+c 부분이 어떻게 될지 모르므로 전체를 다 봐야하는 것이다.

 

예를들어

- 100 -25 0 100 이 있을 경우, 단순히 가장 작은 수와 가장 큰 수를 고르는 방식으로는

max(| -100+50+100 |, |-100+0100|) = 50이 된다.

하지만 실제론 2번째 수를 a로 고른 |-25+0+100| = 75가 답이다.

 

3. 그럼 로직은 다음과 같다.

 

A. 일단 정렬한다. 예제 입력 1을 기준으로 보겠다.

 

B. 일단은 c를 맨 마지막에 두고 a와 b를 다음과 같이 살펴본다.

C. 이번엔 a를 고정하고 b와 c를 다음과 같이 살펴본다.

이 때 매번 a,b,c에 대해 |a-2b+c|을 구해 그 중 최대값이 답이 된다.