[백준 / Python] 27277번 장기자랑

문제

즐거운 설날을 맞아 부대 장기자랑 행사가 개최된다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.

  장기자랑 행사의 총관리자는 공연하는 병사들의 장기자랑 실력을 토대로 행사를 준비하던 중, 아무래도 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담감을 느껴 본 실력을 발휘하지 못할 것이라는 고민을 하게 되었다. 이에 총관리자는 각 병사의 장기자랑 실력을 순서대로 $a_1, a_2, \cdots, a_n$이라고 할 때, $2\leq i\leq N$에 대하여 $i$번째 공연자는 실력을 $\max\left(0,a_i-a_{i-1}\right)$만큼만 발휘할 수 있을 것이라는 가설을 세웠다. 이때, 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다.

  위 가설에 따라, 총관리자는 병사들이 발휘할 수 있는 실력의 합이 최대가 되게끔 공연순서를 배치하고자 한다. 적절한 순서로 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 구하여라.

입력

첫 번째 줄에 병사의 수 $N$이 주어진다. $(1\leq N\leq 100\,000)$ 

두 번째 줄에 $N$명의 병사들의 장기자랑 실력을 나타내는 정수 $a_i$가 공백으로 구분되어 주어진다. $(1\leq a_i\leq 10\,000)$ 

출력

적절한 순서로 $N$명의 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 출력한다.

---

예제

입력

6
1 4 3 5 6 2

출력 

12

---

반응형

---

n = int(input())
data = list(map(int,input().split()))
data.sort()
data = data[::-1]

start = 0
end = n - 1
after_data = []

while True:
    if end < start:
        break
    after_data.append(data[start])
    after_data.append(data[end])
    start += 1
    end -= 1
    

temp = 0
answer = 0 
for i in after_data:
    if temp < i:
        answer += i - temp 
    temp = i
        
print(answer)

---

백준 제 1회 보라매컵 본선 A번 문제이다. 

 

간단하게 실력이 가장 높은 사람, 가장 낮은 사람, 두번째로 높은 사람, 두번째로 낮은 사람 , . . . , 으로 배치를 하면 된다.

 

예를 들어 1, 2, 3, 4, 5, 6이 주어졌을때

리스트를 [6, 1, 5, 2, 4, 3]로 만든다면 병사가 발휘할 수 있는 실력의 최대 합이 되게 된다.