[HackerRank] Marc's Cakewalk

Practice > Algorithms > Greedy

code

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

• 가장 큰 값부터 2^0 ~ 2^n까지 곱하여 더해주는 문제이다.
• 따라서 C++ STL에 있는 Sort함수와 greater<>를 사용하여 내림차순 정렬을 구현하였다. (C++14를 지원하는 이전 버전까지는 greater<>에 명시적으로 타입을 지정해 주어야 한다.)
• 정렬이 끝난 뒤 배열의 크기만큼 2^i * calorie[i]의 합을 구하고 반환하였다.

결과