Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 인턴 후기
- 3단계 지역 DB
- mysql
- 방명록 만들기
- JSTL
- 소프트웨어 개발보안 경진대회
- webhacking 처음
- Database
- EER
- 동읍면 DB
- 정보보호병 후기
- spring
- 소개딩
- Layered Architecture
- riceteacatpanda
- frontend
- jsp
- 네이버 인턴
- reversing.kr
- ㅁㅇㅂ??ㅇㅈㄷ ㅎㅇㅌ...
- 행정지역 DB
- 메모리 포랜식
- Forensic 절차
- SessionAttribute
- react
- PyAmdecoder
- Django
- DBMS
- restapi
- 인턴 지원
Archives
- Today
- Total
웹찢남
[백준 1202 보석 도둑 문제] PYTHON 본문
우선 보석 리스트와 가방 리스트를 받아 정렬한다.
그 후 힙을 사용하여 문제를 해결해야한다.
가방을 기준으로 for문을 돌리는데 이때 가방은 sort되어 무게가 작은 순으료 값이 나온다.
여기서 생각해야 할 점은 보석도 무게를 기준으로 sort 했기 때문에
보석을 heap에 넣어 놓고 다음 for 문 루프를 돌아도 heap에 있는 보석은 다음 가방 속에도 들어갈 수 있다.
그렇다면 heap에 보석을 넣을 때 maxheap으로 값을 넣고
for문이 돌때마다 가방에 들어갈 수 있는 보석을 업데이트 하며
heap 속에 들어있는 가장 가치있는 보석을 pop 하여 result에 값을 더하면
답이 나오게 된다.
처음에는 단순히 이중 포문으로 문제를 해결하려 했으나, 역시나 안된다.
import sys
import heapq
input = sys.stdin.readline
Nlists = []
Klists = []
N, K = map(int, input().split())
for _ in range(N):
a, b = map(int, input().split())
Nlists.append([a, b])
for _ in range(K):
c = int(input())
Klists.append(c)
Nlists.sort()
Klists.sort()
result = 0
tmp = []
for Klist in Klists:
while Nlists and Klist >= Nlists[0][0]:
heapq.heappush(tmp, -Nlists[0][1])
heapq.heappop(Nlists)
if tmp:
result += heapq.heappop(tmp)
elif not Nlists:
break
print(-result)
'백준 Algorithm' 카테고리의 다른 글
[백준 1937 욕심쟁이 판다 문제] PYTHON (0) | 2021.09.10 |
---|---|
[백준 1744 수 묶기 문제] PYTHON (0) | 2021.09.10 |
[백준 4358 생태학 문제] PYTHON (0) | 2021.09.09 |
[백준 1309 동물원 문제] PYTHON (0) | 2021.09.07 |
[백준 5557 1학년 문제] PYTHON (0) | 2021.08.25 |
Comments