[백준][C++] 20115 에너지 드링크

20115. 에너지 드링크

20115번: 에너지 드링크

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

시간 초과로 고생했던 문제... 반복문에 sort 함수를 쓴 내가 잘못이었다 ㅠ_ㅠ

 

임의의 두 에너지 드링크를 합칠 때, 한쪽 에너지 드링크는 1/2만 합칠 수 있으므로 가장 큰 에너지 드링크와 가장 작은 에너지 드링크를 합쳐 작은 쪽을 버리는 것이 효율적이라고 생각했다.

 

알고리즘

1. 에너지 드링크들이 있는 배열을 오름차순으로 정렬한다.
2. (가장 큰 요소 + 가장 작은 요소/2)한 값을 저장한다.
3. 앞뒤에 있는 요소를 제거하고, 대신에 저장한 요소를 배열에 저장한다.
4. 배열의 크기가 1이 될 때까지 1~3을 반복한다.

 

앞뒤에 있는 요소를 원활하게 불러오고 제거할 수 있도록 deque를 사용했고, algorithm 헤더의 sort 함수를 사용했다.

 

while (drinks.size() != 1)
{
    // 오름차순 정렬
    sort(drinks.begin(), drinks.end());

    // (가장 큰 요소 + 가장 작 요소/2)
    double drink = drinks.back() + (double)(drinks.front() / 2);

    drinks.pop_back();
    drinks.pop_front();

    drinks.push_back(drink);
}

cout << drinks.front();

 

이렇게 코드를 반복문에서 O(n long n)의 sort 함수를 불러주면서 시간 초과가 나게 되는 것이다...

 

따라서 반복문에 들어오기 전에만 sort 함수를 불러 오름차순 정렬을 하고

반복문에서는 새로 만든 음료수의 자리만 정해주었다. (O(N)

 

 

코드

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

int main()
{
	ios_base::sync_with_stdio(false);  cout.tie(NULL); cin.tie(NULL);

	int len;
	deque<double> drinks;

	cin >> len;

	for (int i = 0; i < len; i++)
	{
		int input;
		cin >> input;
		drinks.push_back(input);
	}

	sort(drinks.begin(), drinks.end());

	while (drinks.size() != 1)
	{
		// (가장 큰 요소 + 가장 작 요소/2)
		double newDrink = drinks.back() + (double)(drinks.front() / 2);
		
		// 합친 원래 값을 제거
		drinks.pop_back();
		drinks.pop_front();

		drinks.push_back(newDrink);

		// 새로 만든 드링크의 적절한 자리를 비교해서 지정 (도장깨기)
		for (int i = drinks.size() - 1; i >= 0; i--)
		{
			if (drinks[i] < drinks.back())
				break;

			else
				swap(drinks[i], drinks.back());
		}
	}

	cout << drinks.front();
}

 

큰 것과 작은 것을 합친다는 극한의 효율 마인드와 시간 초과로 모든 요소를 정렬하지 않고 새로 만든 음료수의 자리만 정해주는 아이디어가 좋았다!! 꼭 기억해둬야지