[엘리스] 점토 놀이

점토 놀이

엘리스씨는 가장 적은 힘을 사용하여 주어진 모든 점토를 합치고 싶어졌습니다. 엘리스씨를 도와 n개의 점토를 하나의 덩이로 합치기 위해 필요한 힘의 크기의 합의 최솟값을 구하는 프로그램을 작성하세요.

만약 무게가 a인 점토와 무게가 b인 점토를 한 덩이가 되도록 합치기 위해서는 a+b의 힘을 들여야 합니다.

[입력값]

• 〔1〕 점토의 개수 n (1≤n≤100,000)
• 〔2〕 n개의 숫자(각 점토의 무게)

[결과값]

모든 점토를 한 덩이로 합치기 위해 필요한 힘의 크기의 합의 최솟값을 출력합니다.

[제한 시간]

5초 이내에 결과가 출력되어야 합니다.

[입력 예시]

4
1 5 7 3

[출력 예시]

29

[예시 설명]

4개의 점토가 있고 각각 1, 5, 7, 3의 무게를 가진다면 다음의 순서대로 합치는 것이 최소가 됩니다. 먼저 1과 3을 합칩니다. 합쳐진 점토의 크기는 4가 되고, 힘 4가 필요합니다. 그 후 4와 5를 합칩니다. 합쳐진 점토의 크기는 9가 되고, 힘 9가 필요합니다. 그 후 마지막으로 7과 9를 합치면, 결과적으로 한 덩이가 남게 되고, 이 때는 힘 16이 필요합니다. 따라서 이 모든 점토를 한 덩이로 합치기 위해 필요한 힘의 크기는 4 + 9 + 16 = 29 입니다.

풀이

• 우선순위 큐를 이용(우선순위 큐에 대한 내용은 https://eda-ai-lab.tistory.com/435에 있습니다)

from heapq import heappush, heappop, heapify

def getMinForce(weights) :
    '''
    n개의 점토를 하나로 합치기 위해 필요한 힘의 합의 최솟값을 반환하는 함수를 작성하세요.
    '''

    result = 0

    # 초기에 sorted하지 않으면 가장 앞에 있는 것을 우선순위가 높은 것으로 인식함 
    # 해결1. weights = heapify(weights)를 사용해서 heap화 시킬 수도 있음 
    # 해결2. weights의 값을 하나씩 뽑아서 heappush로 넣는 방법도 존재 
    # 해결3. 정렬 
    weights = sorted(weights)

    while len(weights) > 1: 
        A = heappop(weights)
        B = heappop(weights)
        result += (A+B)
        heappush(weights, (A+B))

    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())

    line = [int(x) for x in input().split()]

    print (getMinForce(line))

if __name__ == '__main__':
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn