[백준 20300번] [🥈3] 서강근육맨 (python)

백준 사이트 링크

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 $N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 $10$개의 운동기구가 있을 경우 PT를 $5$번 받으면 모든 기구를 다 사용할 수 있다. $9$개의 운동기구가 있는 경우에도 PT를 $5$번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 $M$을 넘지 않도록 하고 싶다. 이때, $M$의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 $N$이 주어진다. ($1 \leq N \leq 10\ 000$)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 $t_1, t_2, \cdots, t_N$가 주어진다. ($0 \leq t_i \leq 10^{18}$)

출력

  $M$의 최솟값을 출력한다.

예제 입력 1

5
1 2 3 4 5

예제 출력 1

5

힌트

PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다.

---

풀이

1. 입력을 받고, 무게를 배열에 저장한다.

2. 배열을 오름차순으로 정렬한다.

3. 배열을 양쪽 끝에서부터 비교하며, 두 개의 포인터를 사용하여 합이 T 이하인 무게들을 찾는다.
   • 왼쪽 포인터는 가장 가벼운 무게를 가리키고, 오른쪽 포인터는 가장 무거운 무게를 가리킨다.
4. 포인터를 이동시키며, 가장 많은 무게를 들 수 있는 경우를 찾는다.
   • 왼쪽 포인터를 오른쪽으로 한 칸 이동하고, 오른쪽 포인터를 왼쪽으로 한 칸 이동하여 다음 조합을 확인한다.
   • 이동한 무게의 합이 T보다 크다면, 오른쪽 포인터만 왼쪽으로 한 칸 이동한다.
   • 두 포인터가 만나면 종료한다.
5. 가장 많은 무게를 들 수 있는 경우를 출력한다.

코드

ver(1)

시간 복잡도는 O(nlogn)

import sys

# 입력값을 더 효율적으로 받기 위해 sys.stdin.readline을 사용합니다.
input = sys.stdin.readline

# 정수 n을 입력받습니다.
n = int(input())

# 정수들을 리스트 t에 입력받고 오름차순으로 정렬합니다.
t = list(map(int, input().split()))
t.sort()

k = 0

if (n % 2) == 1:  # n이 홀수인 경우
    # 중간 값과 대칭되는 원소들 중 큰 값을 선택하여 k에 저장합니다.
    for i in range((n-1) // 2):
        k = max((t[i] + t[n-i-2]), k)
    print(k)
else:  # n이 짝수인 경우
    # 중간 값을 기준으로 좌우 대칭되는 원소들 중 큰 값을 선택하여 k에 저장합니다.
    for i in range(n // 2):
        k = max((t[i] + t[n-i-1]), k)
    print(k)

ver(2)

시간 복잡도는 O(nlogn)

import sys

# 입력값을 더 효율적으로 받기 위해 sys.stdin.readline을 사용합니다.
input = sys.stdin.readline

# 정수 n을 입력받습니다.
n = int(input())

# 정수들을 리스트 t에 입력받고 오름차순으로 정렬합니다.
t = list(map(int, input().split()))
t.sort()

# 합을 저장할 리스트 k와 합이 홀수인 경우를 처리하기 위한 조건문을 설정합니다.
cnt = 0
k = []
if (len(t) % 2) == 1:
    k.append(t.pop(-1))

# t 리스트의 원소들을 순회하며 가장 큰 합을 계산합니다.
for i in range(len(t)):
    # t[i]가 t의 대칭되는 원소보다 큰 경우에는 더 이상 계산하지 않고 종료합니다.
    if t[i] > t[(len(t)-i-1)]:
        break
    # t[i]와 대칭되는 원소의 합을 k 리스트에 추가합니다.
    k.append(t[i]+t[(len(t)-i-1)])

# k 리스트의 최댓값을 출력합니다.
print(max(k))