[알고리즘/그리디] 20300번 : 서강 근육맨 - python

링크 : https://www.acmicpc.net/problem/20300

20300번: 서강근육맨

 

---

• 문제
• 소요시간: 15분 24초

---

• 설계하기(접근방법) 

1. 입력받기

기구의 개수와 기구의 피로도를 입력받는다

 

2. 알고리즘 해석

두 기구의 합의 조합을 모두 했을 때

그 최대값이 최소가 되도록 해야 한다.

 

먼저 리스트를 정렬한다

정렬하면

 

1,2,3,4......10과 같은 형태로 정렬될 것이다

가장 큰 수 인 10 과 짝을 지었을 때 가장 작은 합을 가질 수 있는 경우는 (1,10)이다

역시 그 다음 수는 9는 2와 짝을 지었을 때 가장 작은 합을 가진다

.... 가운데의 원소끼리 짝이 지어질때까지 반복한다

 

리스트의 원소 수가 홀수인 경우와 짝수인 경우로 나눈다

1) 홀수인 경우

가장 큰 수인 마지막 숫자를 pop해주고 저장해놓는다.

그리고 2)의 단계로 넘어간다

2) 단계를 수행한 후 pop한 원소와 최대값을 비교하여

그 중의 큰 값을 구한다.

2) 짝수인 경우

리스트의 가장 작은 원소, 가장 큰 원소를 더해주고

그다음 작은 원소, 2번째로 큰 원소

..... 를 더해나가며

그 중 최대값을 구한다

 

 

 

---

• 코드(출력)

n = int(input())
machine = list(map(int, input().split()))

machine.sort()


def find_max(machine):
    max_val = 0
    for i in range(len(machine)//2):
        temp = machine[i] + machine[len(machine)-1-i]
        if (temp > max_val):
            max_val = temp
    return max_val


if len(machine) % 2 == 0:
    result = find_max(machine)
    print(result)
else:
    big = machine.pop()
    result = find_max(machine)
    if result > big:
        print(result)
    else:
        print(big)

 

---

• 얻어갈 부분