문제

코드1

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

long marcsCakewalk(vector<int> calorie)
{
	long sum = 0;
	long pow = 1;
	int n; cin >> n;
        int num;	
	for (int i = 0; i < n; i++){ 
		cin >> num; 
		calorie.push_back(num);
	}
	sort(calorie.begin(), calorie.end(), greater<>());
	for (int i = 0; i < calorie.size(); i++){
		for (int j = 0; j < i; j++){
			pow *= 2;
		}
		sum += calorie[i] * pow;
		pow = 1;
	}
	return sum;
}

코드2

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

long marcsCakewalk(vector<int> calorie)
{
    long sum = 0;
    int n;
    cin >> n;
    vector<long> pow(n, 1);
    int num;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        calorie.push_back(num);
    }
    sort(calorie.begin(), calorie.end(), greater<>());
    for (int i = 0; i < calorie.size(); i++)
    {
        sum += calorie[i] * pow[i];
	    if(i != calorie.size()-1) pow[i+1] = pow[i]*2;
        
    }
    return sum;
}

코드1에서 하나의 테스트 케이스가 안돌아 가는 문제가 발생했다.

Input
40
801 234 536 747 172 590 833 847 509 429 666 411 609 894 348 254 814 767 647 965 711 801 852 781 972 390 218 290 508 174 55 714 442 284 745 872 46 131 833 315
Output
84350424920174

그래서 코드2를 만들었다. 코드2는 memoization을 활용해서 동적으로 square값을 기록해서 연산해서 시간 복잡도가 O(n)이 나오도록 만들었다.!