[Softeer] 금고털이

쉬운 문제다. 단순히 무게당 가격이 큰 순서로 정렬해줘서, 금속무게가 배냥에 넣을 수 있는 무게보다 작으면 금속 전부를 넣고, 금속무게가 배냥에 넣을수 있는 무게를 넘으면, 배냥에 넣을 수 있는 무게 만큼의 금속을 넣으면 된다.

이렇게 간단한 문제를 왜!! 벨로그에 남기냐면,, 계속 시간초과가 터지기 때문이다...
분명 제한이 최대 10^6인데, 시간복잡도는 O(nlogn)로 도저히 3초의 시간을 넘지 않는다고 생각하는데, 계속 몇몇 테케에서 걸리는 것이다.

그래서 시간을 최소화 하기위해 아래와 같이 코드를 짜봤다.

# 3초 제한에 nlogn 복잡도 인데, 초과나는것이 이해가 안가지만
# 최소한의 시간을 쓸 수 있도록 하자
# 
import sys
input=sys.stdin.readline
w,n = map(int, input().split())

jewel=[list(map(int, input().split()))for _ in range(n)]
jewel=sorted(jewel, key = lambda x:x[1], reverse=True)
price=0

for mj,pi in jewel:
    if w>mj:
        price+=mj*pi
        w-=mj
    else:
        price+=w*pi
        break
print(price)

여기서 핵심은 뒤의 것(가격)만 정렬하는 lambda이다.
불필요한 정렬 연산을 줄여줌으로써, 시간복잡도를 줄인다.