[소프티어] 금고털이
T
TikaToka
Algorithm
All about CS Algorithm
Al
All about TIKAAlgorithm
이 문제 같은 경우는 그냥 직관적으로 풀어도 통과하기도 한다 (실행 때 마다의 미세한 시간 차이 때문에)
Naive Sol
import sys
w, n = map(int, input().split())
golds = []
for i in range(n):
golds.append(list(map(int, input().split())))
golds.sort(key=lambda x: -x[1])
gram = 0
answer = 0
for i in golds:
if gram >= w:
break
if gram + i[0] <= w:
gram += i[0]
answer += i[0] * i[1]
else:
temp = w - gram
gram = w
answer += temp * i[1]
print(answer)
하지만 우리는 최대부터 고려하면 되기 때문에, 그때의 최대만을 계속 뽑아낼 수 있는 heap을 쓸 수 있다
Sol
import heapq
w, n = map(int, input().split())
# 1g당 금 가격의 역순으로 최대 힙 구성
golds = []
for _ in range(n):
weight, price = map(int, input().split())
heapq.heappush(golds, (-price, weight))
gram = 0
answer = 0
while golds and gram < w:
neg_price, weight = heapq.heappop(golds)
price = -neg_price # 원래의 가격 복원
if gram + weight <= w:
gram += weight
answer += weight * price
else:
remaining = w - gram
answer += remaining * price
break
print(answer)
Al
Subscribe to 'All about TIKA'
AI Tech Blog with Curriculum Vitae
Subscribe
Other posts in 'Algorithm'
[소프티어] CPTI
O(n^2m)이라서 틀리는 코
[코드 트리] 트리 판별
문제에서 루트노트 1개인지 루트를 제외한 노드들이 parent가 항상 1개인지 전부 연결되어있는지 를 체크해야한다 참고로 유방향 그래프임을 기억해야 한다. 1번은 간선 정보를 저장하며 1) 그 번호가 사용되는지, 몇개의 parent가 있는지 기록해둔다 이를 통해 root를 찾을 수 있고 1개인지 체크 가능하다 2번은 간선 정보를 통해 확인 가능하다 3번은 dfs를 돌려서 전부 visited되는지로 확인 가능하다 solution
[코드트리] 1, 2, 5 더하기
쉬운 문제라고 하나, 기억할 부분이 있어서 간단하게 정리 solution dp를 경우의 수를 저장 하는것 여기서 순서를 고려하기 떄문에,. i-1, i-2, i-5 번째의 경우를 더해주기만 하면 됨 또한, 그렇게 때문에 dp[0] = 1 로 정해야함. (0을 만드는 방법의 수가 1가지라고 생각)
Made with Slashpage