[BOJ: 20300] - Python / 파이썬 - 서강근육맨

o_jooon_·2024년 1월 29일
0

BOJ

목록 보기
19/49
post-thumbnail

서론

그리디 문제입니다.
각 날짜 별 일어나는 근손실을 계산 후, 가장 큰 근손실의 값이 최소가 되게 하는 문제입니다.
문제 자체가 설명하기 조금 헷갈리네요.

난이도

실버 3


문제

조건

시간 제한메모리 제한
1 초 (추가 시간 없음)1024 MB

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

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

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

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


입력

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


출력

MM의 최솟값을 출력한다.


예시

예제 입력 1

5
1 2 3 4 5

예제 출력 1

5

PT 첫째 날에 1144를 선택하고, 둘째 날에 2233을 선택하고, 마지막 날에 55를 선택하면 MM55가 되며, 이때가 MM이 최소일 때이다.


풀이

짧은 버전 기준으로 하겠습니다. (홀수 짝수 따로 처리해주는게 동일)

  1. 입력 받은 숫자를 오름차순으로 정렬해준다.
  2. n이 홀수인지 짝수인지에 따라 ans와 m을 초기화 해준다.
    짝수의 경우 현재 기준 가장 작은 수와 가장 큰 수의 합을 n의 절반만큼 해주면 모두 탐색이 가능하고,
    홀수의 경우 절반만큼 탐색해도 하나가 남기 때문에 가장 큰 수를 따로 뺀 후 나머지를 짝수의 경우처럼 탐색한다.
  3. 탐색하면서 나온 수 중 가장 큰 수를 출력한다.

근손실이 최소가 되게 하려면, 운동 기간 동안 날짜 별로 다른 기구를 이용하면서 가장 큰 근손실이 최소가 되게 해야합니다.
이게 무슨 소리냐면, 1 2 3 4에서 처음과 끝인 1과 4가 아닌 1과 2를 고르면 3과 4만 남게되어 운동 기간동안 얻는 최대 근손실이 7이 되어버립니다. 하지만 1과 4, 2와 3을 고르면 최대 근손실은 5가 되죠.

코드

# 불편한(긴) 버전 - 시간 48 ms
n = int(input())
machines = sorted(list(map(int, input().split())))	# 근손실 정도 오름차순 정렬
ans = 0

if n % 2 == 0:				# n이 짝수라면
    for i in range(n // 2):	# n의 절반까지만 탐색(반대 인덱스도 계산하기 때문)
		#  근손실의 합이 최소가 되게 하려면 가장 작은 수와 가장 큰 수를 차례대로 더해주면 됨
        ans = max(ans, machines[i] + machines[n - 1 - i])
else:								# n이 홀수라면
    ans = max(ans, machines.pop())	# 근손실이 가장 큰 기구를 따로 계산
    for i in range(n // 2):
    	# 홀수의 경우 가장 마지막 수를 제외하고 탐색을 하기 때문에 n-2-i를 해줌
        ans = max(ans, machines[i] + machines[n - 2 - i])

print(ans)

# 편한(짧은) 버전 - 시간 56 ms
n = int(input())
machines = sorted(list(map(int, input().split())))
# 위에서 홀수의 경우 근손실이 가장 큰 기구를 따로 계산하고 n-2-i를 해준 경우를 초기에 계산
ans, m = (0, n) if n % 2 == 0 else (machines[-1], n - 1)

for i in range(n // 2):
	# 초기에 홀짝 여부에 따른 값을 정해주었기 때문에 짝수 홀수 모두 한 줄로 가능
	ans = max(ans, machines[i] + machines[m - 1 - i])

# print(ans)

실행 결과

profile
안녕하세요.

0개의 댓글