[HackerRank] Marc's Cakewalk (마크케이크웍) Greedy 문제

 

문제

마크는 결혼식에서 케이크를 먹고 싶어 합니다.

하지만 마크의 다이어트를 돕기 위해서, 그의 친구들은 그가 먹는 각 케이크의 칼로리에 대해 벌칙을 부여하기로 했습니다.

마크가 먹는 각 케이크에 대해, 그 케이크의 칼로리에 2의 j승을 곱하여 벌칙 점수를 계산합니다.

여기서 j는 마크가 먹은 케이크의 순서이며, 가장 먼저 먹은 케이크의 j는 0이고, 두 번째로 먹은 케이크의 j는 1입니다.

 

마크가 먹을 케이크의 칼로리가 주어졌을 때, 그가 얻을 수 있는 최소한의 벌칙 점수를 계산하세요.

 

입력:

3
5 10 7

 

출력:

44

 

예시:

 

 

문제 해결 전략

 

칼로리 내림차순 정렬:

• 벌칙 점수를 최소화하기 위해서는 칼로리가 높은 케이크를 먼저 먹어야 합니다.

벌칙 점수 계산:

• 내림차순으로 정렬된 칼로리 배열을 사용하여, 각 케이크에 대해 2의 j승을 곱하여 벌칙 점수를 계산합니다.

최소 점수 계산:

• 모든 벌칙 점수를 합산하여 최소 벌칙 점수를 출력합니다.

 

풀이

반복문을 통해 2의 승수를 구하는 ( 2 ** i ) 활용

def marcsCakewalk(calories):
    # 칼로리를 내림차순으로 정렬
    calories.sort(reverse=True)
    
    # 최소 벌칙 점수 계산
    min_penalty = 0
    for i in range(len(calories)):
        min_penalty += (2 ** i) * calories[i]
    
    return min_penalty

# 예시 실행
calories = [7, 4, 9, 6]
print(marcsCakewalk(calories))  
# 출력: 79

 

문제 링크

 

https://www.hackerrank.com/challenges/marcs-cakewalk/problem?isFullScreen=true

Marc's Cakewalk | HackerRank