[Python] 백준 20117번_호반우 상인의 이상한 품질 계산법

https://www.acmicpc.net/problem/20117

20117번: 호반우 상인의 이상한 품질 계산법

 

• 경북대 특산품 호반우는 품질에 따라 등급이 숫자로 매겨짐
• 호반우 상인들은 N개의 호반우를 팔려고 함
• 호반우는 개별적으로 팔 수도 있지만 묶음으로 팔 수도 있음
• 이 때 묶음이라 함은 호반우들의 어떤 부분집합을 말함
• 하나의 호반우를 팔 때 기존의 계산법으로는 품질만큼의 가격으로 팔리게 됨
• 따라서 묶어파나 개별적으로 파나 상인이 벌 수 있는 총 금액은 차이가 없었음
• 호반우 상인들은 새로운 품질 계산법을 개발해냄
• 호반우를 묶음으로 팔 때는 모든 호반우의 품질을 묶음의 '중앙값'으로 결정
• 이 때 묶음이 짝수인 경우 묶음 안에 있는 호반우를 품질을 기준으로 정렬했을 때 (묶음 개수/2+1)번째 호반우를 중앙값으로 정의하고 홀수인 경우 ((묶음 개수+1)/2)번째 호반우를 중간값으로 정의
• 호반우들을 팔아서 얻을 수 있는 최대 이익을 계산하기

• 입력
  • 첫 번째 줄에 호반우의 개수 N (1 ≤ N ≤ 100,000)이 주어짐
  • 두 번째 줄에 공백으로 구분된 N개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 1,000)가 주어지는데 이 숫자는 각 호반우의 품질을 나타냄
• 출력
  • 모든 호반우를 팔았을 때 얻을 수 있는 최대 이익을 출력
• 시간 제한: 1초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

4
4 2 8 9
        -> 34
"""

 

# 호반우의 품질이 [1, 2, 3, 4]
# -> 중간값인 3으로 모든 호반우의 품질을 계산

# => 이 묶음의 총 가격은 3 × 4 = 12

# 품질이 [6, 3, 9] 
# -> 중간값인 6으로 모든 호반우의 품질을 계산

# => 이 묶음의 총 가격은 6 × 3 = 18

 

 

## 의사코드 ##

# 오름차순 정렬

# n이 짝수 -> 중앙값: (n/2+1)번째 호반우

# n이 홀수 -> 중앙값: ((n+1)/2)번째 호반우

# 최대 이익 = 중앙값 * n

 

 

 

첫 번째 시도

 

# 호반우의 개수
n = int(input()) 
# 호반우들의 품질
hos = list(map(int, input().split()))

# 호반우 품질을 오름차순 정렬
hos.sort()

# 짝수인 경우
if n % 2 == 0:
    # (n/2+1)번째 호반우 
    mid = hos[(n//2)]
# 홀수인 경우
else:
    # ((n+1)/2)번째 호반우
    mid = hos[(n+1)//2 - 1]

# 묶어서 판매할 경우 = 중앙값 * n 
# 개별적으로 판매할 경우 = 각 호반우의 품질만큼의 가격
# 최대 이익 = 묶어서 판 금액과 개별적으로 판 금액 중 더 큰 값
print(max(mid * n, sum(hos)))

 

 

-> 틀림

 

노트에서 설명된 예시를 보고 

묶음을 품질 리스트 전체인 묶음 하나만 만든다고 잘못 이해함...

 

 

 

통과한 코드

 

# 호반우의 개수
n = int(input())
# 호반우들의 품질
hos = list(map(int, input().split()))
# 호반우 품질을 오름차순 정렬
hos.sort()

# 가장 작은 값과 가장 큰 값을 하나의 묶음으로 만들어 가장 작은 값을 가장 큰 값으로 바꿔서 더하기
# -> 품질 리스트의 끝 값들만 필요
# 작은 값들을 모두 큰 값들로 바꿔줄 것이기 때문에 큰 값들만 더한 다음 곱하기 2
ans = sum(hos[(n+1)//2:]) * 2

# 개수가 홀수인 경우
if n % 2 == 1:
    # 마지막 남은 품질 리스트의 가운데에 위치한 값 더해주기
    ans += hos[n//2]

print(ans)

 

 

• 가장 작은 값과 가장 큰 값을 하나의 묶음으로 
  • ex) (2, 8) (4, 9)
    • => 8 * 2 + 9 * 2 = 34
  • -> 작은 값들이 큰 값들로 바뀔 것이기 때문에 오름차순 정렬된 품질 리스트의 끝 값들을 더한 다음 2를 곱해주면 됨
• 호반우의 개수가 홀수인 경우, 마지막 하나가 남음
  • 마지막으로 남은 값을 더해주기

 

 

• 과정 확인

"""
호반우의 개수(n): 4
정렬된 품질 리스트(hos): [2, 4, 8, 9] 

인덱스((n+1)//2): 2
품질 리스트의 끝 값들: [8, 9]
최대 이익 = 품질 리스트의 끝 값들을 더한 값(17) * 2
  =>  34 

34
"""

 

 

 

 

 

참고)

 

https://www.acmicpc.net/board/view/71085

글 읽기 - 문제 이해가 안됩니다.

 

https://eboong.tistory.com/470?category=909716

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