[C++] 백준 20115번 드링크

1. 문제이해

20115번: 에너지 드링크 (acmicpc.net)

20115번: 에너지 드링크

 

에너지드링크의 수와 각 에너지드링크의 양이 주어진다.

페인이는 에너지 드링크 두개를 골라, 하나의 에너지 드링크를 다른 한쪽에 모두 붓고,

붓는 과정에서 손이 떨려 절반을 흘리게 된다고 한다.

위 과정을 반복할 때, 페인이가 만들 수 있는 에너지 드링크의 최대 양은 얼마인지 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

페인이는 에너지 드링크들 중 두개를 골라 하나의 에너지드링크를 다른 한쪽에 모두 붓는다.

단, 절반은 페인이가 흘리게 되므로, 에너지 드링크의 절반만 다른 한쪽에 붓게 되는 셈이다.

이러한 과정을 모두 거쳐 에너지 드링크를 모두 사용해 최대 양을 구하려고 할때,

합쳐진 에너지 드링크의 양이 최대가 되려면 어떻게 해야할까?

 

풀이 방법은 간단하다.

고른 2개의 에너지 드링크 중, 양이 많은 드링크 쪽에 적은 드링크의 절반을 부으면 된다.

 

그렇다면, 두개의 에너지 드링크는 어떤 방식으로 골라야 할까?

주어진 에너지 드링크들 중 양이 최대인 것과 나머지들 중 하나를 고르면 된다.

(아래 예제에서는 최대값과 최소값을 골라 더해나갔는데,

최대값만 구해주면, 나머지 값들은 어차피 다 절반씩 더해나갈거라,

어떤 값을 먼저 더하든 중요하지 않다.)

 

위의 예제 1의 경우에 적용시켜보자.

에너지 드링크의 양은 3, 2, 10, 9, 6 이다.

정렬하면 2, 3, 6, 9, 10 이고,

여기서 양이 가장 많은 에너지 드링크는 10 이다.

10 을 기준으로, 가장 양이 적은 드링크부터 순서대로 여기에 붓는다고 하자.

 

10 + (2 / 1) = 11

 

이 된다.

11이 또다른 최대값이 되므로, 여기에 다른 음료를 다시 붓고,

이러한 과정을 반복한다.

 

11 + (3 / 1) = 12.5

12.5 + (6 / 3) = 15.5

15.5 + (9 / 2) = 20

 

따라서, 위의 경우 페인이가 만들 수 있는 에너지 드링크의 최대 양은 20이 된다.

위 두 가지 방법을 적용해 코드도 그대로 구현해보았다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N;	// 에너지드링크 수 
	double energy_drink[100000];	// 에너지 드링크의 양
	double max;	// 합쳐진 에너지 드링크의 최대 양

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> energy_drink[i];
	}

	// 주어진 에너지 드링크들 중
	// 양이 제일 많은 드링크를 찾기 위해 정렬
	sort(energy_drink, energy_drink + N);

	// 정렬된 값중 마지막 값이 제일 양이 많은 드링크
	// 이 값을 기준으로 나머지 드링크들을 여기에 붓는다.
	max = energy_drink[N - 1];

	for (int i = 0; i < N - 1; i++) {
		// 가장 큰 값에 다른 작은 값의 드링크들을 모두 붓는다.
		// 단, 붓는 과정에서 절반씩 흘린다고 했으므로, / 2
		max += (energy_drink[i] / 2);
	}

	cout << max;

	return 0;
}

 

에너지 드링크의 개수(N)와 각 에너지 드링크의 양(energy_drink[i])을 입력받는다.

(에저지 드링크의 양은 결과값이 소수점까지 반영되므로 double 형으로 해주었다.)

입력받은 에너지 드링크의 양 중, 가장 큰 값을 찾기 위해 정렬한 후,

정렬된 값들 중 마지막 값이 가장 큰 값이므로 해당 값을 max에 넣어준다.

 

for문을 통해 정렬된 처음 값부터 마지막 전 값까지 절반씩 max에 더해나간다.

(최대값에 나머지 에너지 드링크의 양들을 절반씩 붓는 과정)

 

 

---

코드가 처음 짠대로 한번에 돌아가면.. 너무 기분이 좋다..🥰

아침부터 상쾌하게 하루를 시작하는 기분이랄까🤗