흙금이네 블로그

[BOJ] 16208 - 귀찮음 (Python) 본문

알고리즘

[BOJ] 16208 - 귀찮음 (Python)

흙금 2023. 3. 23. 13:38

 

 

아이디어

 

최소 비용으로 막대를 자르기 위해서는 막대 길이가 작은 것부터 잘라야 한다.

 

 

풀이 #1

 

sorted 함수 또는 sort 메서드를 이용하여 정렬한 후 비용을 계산한다.

 

def solution():
    n = int(input())
    a = sorted(map(int, input().split()))
    total = sum(a)
    res = 0
    for i in range(n-1):
        total -= a[i]
        res += a[i]*total
    print(res)

solution()

 

 

 

풀이 #2

 

계수 정렬을 이용하여 정렬한 후 비용을 계산한다.

 

def solution():
    _ = int(input())
    cnt_list = [0]*102
    total = 0
    for a in map(int, input().split()):
        cnt_list[a] += 1
        total += a
    res = 0
    for a in range(1, 102):
        for _ in range(cnt_list[a]):
            total -= a
            res += a*total
    print(res)

solution()

 

Comments