[20117] 호반우 상인의 이상한 품질 계산법 in python

 

> 정렬

 

처음에 이 문제를 보고

묶음이 여러개 있어도 된다는건가?라는 생각과 함께

묶음이 짝수인 경우 

묶음 안에 있는 호반우를 품질을 기준으로 정렬했을 때

(묶음개수/2+1)번쨰 호반우를 중앙값으로 정의해야한다는 글을 보고

묶음 개수가 배열에서 내가 정한 묶음의 개수를 의미하는건가..라는 생각과 함께

한참 헤매고 있었다.

 

그런데 묶음의 개수가 이 의미가 아니었다.

만약 배열이 [2,4,8,9]라고 가정하자.

그러면, 지금 내가 2랑 9를 묶으면 이 묶음의 총 길이는 2이다.

짝수이므로 중앙값은 2/2+1 = 2가 되니까 

배열의 2번째 값인 9가 중앙값이 되는 것이다.

 

만약 내가 [2,4,9]라고 묶었다고 가정하면 총 길이는 3이다.

홀수이므로 중앙값은 3+1/2=2이고

우리는 최대 이익을 만들어야하기 때문에 위와 같이 묶으면 안된다.

 

 

즉 묶는 기준은 이와 같다.

1. 가장 작은 값과 가장 큰 값을 한 묶음으로 만든다.

2. 만약 값이 1개가 남는다면? 호반우의 개수가 홀수인 경우다.

이럴땐 이 값은 그냥 그대로 더해주면 그만인 것!

 

여기서 포인트는

가장 작은값과 가장 큰 값을 한 묶음으로 만든다는거!

 

 

n = int(input())
array = sorted(list(map(int, input().split())))
left =0
right = n - 1
if n % 2 == 0:
    answer = 0
    for i in range(n // 2):
        answer += array[right - i] * 2
    print(answer)
    exit()
else:
    answer = 0
    for i in range(n // 2 + 1):
        if i == n // 2:
            answer += array[right - i]
            print(answer)
            exit()
        answer += array[right - i] * 2

---

좀 더 빠르고 간편한 방법을 찾아왔다.

어차피 배열의 끝값만 필요한거니까

굳이 위처럼 하나하나 작업해줄 필요가 없었다! 띠용!

 

이렇게 간단해지다니..

 

배열 [2,4,8,9]를 생각해보면,

일단 array[(n+1)//2:] -> array[2:] -> array[2],array[3] -> 8,9

끝값만 모인다!

 

이걸 sum함수로 묶어주고 거기에 *2를 해주면 끝!

*2를 해주는 이유는 가장 작은값도 가장 큰값으로 바꿔서 더해줘야하므로

 

만약 총 배열의 수가 홀수라면?

배열의 가운데 있는 값만 따로 더해주면 끝!

n = int(input())
array = sorted(list(map(int, input().split())))
answer=sum(array[(n+1)//2:])*2
if n%2==1:
    answer+=array[n//2]
print(answer)