[BOJ] 백준 20115번 Python

백준 20115번 Python

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

 

문제

---

페인은 에너지 드링크를 좋아하는 회사원이다.

에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어

피로 회복에 도움을 주는 에너지 보충 음료수이다.

야근을 마치고 한밤중에 퇴근하니 벌써 새벽 1시.

하지만 주말은 아직 멀었고, 다음 날에도 정시에 출근해야 하는 페인은 오늘도 에너지 드링크를 찾는다.

반복되는 야근에 지친 나머지, 평소보다 더 많은 에너지와 피로 회복이 필요했던 페인은

집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한 번에 마시려 한다.

페인이 에너지 드링크들을 합치는 과정은 다음과 같다.

1. 임의의 서로 다른 두 에너지 드링크를 고른다.
   
   
2. 한쪽 에너지 드링크를 다른 쪽 에너지 드링크에 모두 붓는다.
   단, 페인은 야근 후유증으로 인해 손이 떨려, 붓는 과정에서 원래 양의 절반을 바닥에 흘리게 된다.
   
   
3. 다 붓고 남은 빈 에너지 드링크는 버린다.
   
   
4. 1~3 과정을 에너지 드링크가 하나만 남을 때까지 반복한다.

예를 들어, 두 에너지 드링크 a, b가 있고, 양이 각각 x_a, x_b라 할 때, 다음 둘 중 하나의 선택을 할 수 있다.

• a의 양을 x_a + (x_b/2)로 만들고, b를 버리기
• b의 양을 x_b + (x_a/2)로 만들고, a를 버리기

페인은 합쳐진 에너지 드링크의 양을 최대로 하려 한다. 불쌍한 페인을 도와주자!

 

입력

---

첫째 줄에 페인이 가지고 있는 에너지 드링크의 수 N이 주어진다. (2 ≤ N ≤ 10⁵)

둘째 줄에 각 에너지 드링크의 양이 공백으로 구분되어 주어진다.

i번째 정수 x_i (1 ≤ x_i ≤ 10⁹)는 에너지 드링크 i의 양이 x_i임을 의미한다.

 

 

출력

---

첫째 줄에 페인이 최대로 만들 수 있는 에너지 드링크의 양을 출력한다.

절대/상대 오차는 10^-5까지 허용한다.

 

반응형

풀이

---

import sys
input = sys.stdin.readline

N = int(input().rstrip())
drink = list(map(int, input().rstrip().split()))
M = max(drink)
print(M + (sum(drink)-M)/2)

 

728x90

정말 간단한 풀이이다.

 

(이게 실버3 문제가 맞나?)

 

문제를 보면 '에너지 드링크를 합칠 때 붓는 과정에서 원래 양의 절반을 바닥에 흘리게 된다' 라는 조건이 있다.

 

이 말은 '에너지드링크를 옮길때마다 양이 1/2배가 된다'라고 해석할 수 있다.

 

에너지 드링크의 양을 최대로하기 위해서 옮기는 과정에서의 손실을 줄여야한다.

 

가장 양이 많은 에너지드링크에 나머지를 하나씩 붓는 방식을 생각할 수 있었다.

 

결과적으로 <가장 양이 많은 에너지 드링크> + <나머지의 절반> 이 문제에서 요구하는 출력임을 알 수 있다.

 

이 문제에서 유일하게 유의해야할 점이 하나 있다.

 

코드를 작성할 때 관성적으로 나누기 표현을 //로 하면 소수점 표기가 안 된다.

 

(//는 정수인 몫을 반환하기 때문에 소수점이 표현이 안 된다.)