[Softeer] 금고털이

탐욕 알고리즘 적용

 

🧑🏻‍💻 me

import sys


if __name__ == '__main__':

    w,n = map(int, input().split())

    info_dict = {}
    for _ in range(n):
        unit_w, unit_p = map(int, input().split())
        
        if unit_p in info_dict.keys():
            info_dict[unit_p] += unit_w
        else:
            info_dict[unit_p] = unit_w


    # 가격을 기준으로 sort
    sort_dic = dict(sorted(info_dict.items(), reverse=True))
    
    # 최종 값어치
    total_price = 0

    # 해당 dic 순회하며 배낭채우기
    for k, v in sort_dic.items():
          
        # 배낭 보다 큰 경우
        if v >= w :
            total_price += w * k
            break
        
        # 배낭 보다 작은경우        
        
        total_price += v * k
        w = w - v      

        
    print(total_price)