SJ_Koding

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐를 사용하는 대표적인 문제인 것 같다. 문제 요약: 여러 장으로 구성된 덱들을 하나로 합칠 때, 최소 비교 횟수로 합칠 수 있는 방법 ex) 10장, 20장, 40장으로 구성된 덱에서 10장짜리와 20장짜리를 합치는데 30번의 비교가 들고 합쳐진 30장과 40장을 합칠때는 70번의 비교가 소요되어 총 100번의 비교가 수행. 만약 10장과 40장을 먼저 합치고 20장과 합친다면 (10+40) + (50 + 20) == 120이 되어 최소..

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 유명한 보석 문제이다. 스터디에서 진행했던 문제이고 그리디 알고리즘을 공부할 수 있는 좋은 문제인 것 같아, 정리차원에서 포스팅한다. 문제 요약: 최대 용량이 다양한 가방들이 주어지고 가방에는 하나의 보석만 담을 수 있다. 보석은 무게와 값어치가 각각 주어지고, 최대 30만개를 훔칠 수 있다. 보석의 무게가 가방의 최대 용량보다 크면 가방에 담을 수 없다. 최대로 훔칠 수 있는 보석의 값어치 총합을 구..