Softeer 연습문제(2단계) - 금고털이

Candidate | Softeer Assessment UI

Candidate | Softeer Assessment UI

 

나의 풀이

import sys

def _main(bag, n_list):
    answer = 0
    for now_w, now_p in n_list:
        if (bag >= now_w):
            bag -= now_w
            answer += (now_w * now_p)
        else:
            answer += (bag * now_p)
            break
    return answer

bag, n_ct = map(int, sys.stdin.readline().rstrip().split())
n_list = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n_ct)]
n_list = sorted(n_list, key=lambda x:-x[1])
print(_main(bag, n_list))

 

시간 복잡도

n_list = sorted(n_list, key=lambda x:-x[1]) : 정렬 알고리즘 ( 선형 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )