Marc's Cakewalk

마크는 컵케이크를 좋아하지만, 건강 관리도 좋아합니다. 컵케이크 하나당 칼로리가 정해져 있고, 마크는 그 칼로리를 소모하기 위해 먼 거리를 걸을 수 있습니다. 만약 마크가 지금까지 먹은 컵케이크는 j. 컵케이크를 먹은 후 그는 적어도 걸어야 할 칼로리 c. 체중을 유지하기 위해 2^j x c마일을 이동했습니다.

예

calorie = [5, 10, 7]

그가 표시된 순서대로 컵케이크를 먹는다면 그가 걸어야 할 마일은 다음과 같습니다.

(2^0 x 5) + (2^1 x 10) + (2^2 x 7) = 5 + 20 + 28 =53.

하지만 이는 최소값이 아니므로 다른 소비 순서를 테스트해야 합니다. 이 경우 최소 마일리지는 다음과 같이 계산됩니다..

(2^0 x 10) + (2^1 x 7) + (2^2 x 5) = 10 + 14 + 22 =44.

각 컵케이크의 칼로리 함량을 고려하여, 마크가 체중을 유지하기 위해 걸어야 하는 최소 거리를 구하세요. 마크는 컵케이크를 원하는 순서대로 먹을 수 있습니다 .

기능 설명

아래 편집기에서 marcsCakewalk 함수를 완성하세요 .

marcsCakewalk에는 다음과 같은 매개변수가 있습니다.

• int calorie[n]: 컵케이크 한 개의 칼로리 수

보고

• 긴: 필요한 최소 마일

입력 형식

첫 번째 줄에는 정수가 포함됩니다. n, 컵케이크의 수 calorie.
두 번째 줄에는 다음이 포함됩니다. n공백으로 구분된 정수 calorie[i].

제약 조건

• 1 ≤ n ≤40
• 1 ≤ c[i] ≤1000

샘플 입력 0

3 
1 3 2

샘플 출력 0

11

설명 0

Marc가 자신의 체중을 유지하기 위해 걸어야 하는 마일 수는 먹는 순서를 통해 최소화 할 수 있습니다.

1. 컵케이크를 먹어요 c1 = 3칼로리, 그래서 miles = 0 + (3x2^0) = 3.
2. 컵케이크를 먹어요 c2 = 2칼로리, 그래서 miles = 3 + (2x2^1) = 7.
3. 컵케이크를 먹어요 c0 = 1칼로리, 그래서 miles = 7 + (1x2^2) = 11.

그런 다음 최종 값을 인쇄합니다. miles, 이는 11, 우리의 대답은 다음과 같습니다.

샘플 입력 1

4 
7 4 9 6

샘플 출력 1

79

설명 1

(2^0 x 9) + (2^1 x 7) + (2^2 x 6) + (2^3x 4) = 9 + 14 + 32 = 79.

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

체중 유지를 위해 컵케이크를 섭취 했을때 체중유지를 위해 걸어야할 거리중 가장 짧은 거리를 구하는 문제

섭취 순서에 따라 해당 섭취 시점에 걸어야할 거리가 달라진다.

 

문제접근

높은 칼로리의 음식을 먼저 먹을 수록 거리가 짧아짐으로 주어진 컵케이크의 칼로리 순서를 내림차순으로 정렬하여 계산한다.

 

public static long marcsCakewalk(List<int> calorie)
    {
        calorie.Sort();
        calorie.Reverse();
        
        long result = 0;
        for(int i = 0; i < calorie.Count(); i++)
        {
            result += (long)(Math.Pow(2, i) * calorie[i]);
        }
        return result;
    }