문제 링크 http://icpc.me/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디로 풀 수 있다. 보석의 정보를 보석의 가격을 기준으로 내림차순으로 정렬한다. 그 후에 처음부터 가격이 높은 것부터 차례대로 무게보다는 크거나 같은 최소 가방을 찾으며 가방을 매칭 시켜주면 된다. 가방을 매칭시켜줄때는 lower_bound를 이용하면 된다. 또한 가방을 매칭시키고 바로 없애주기 위해 multiset 자료구조를 사용한다. cf) 모..

문제 링크 http://icpc.me/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 풀이 그리디로 풀 수 있다. 현재 가지고 있는 꽃이 죽기 전에 피고, 가장 오랫동안 살아있는 꽃을 고르면 된다. 날짜는 구현의 편의를 위해 달에 100을 곱하고 일을 더했다. ex) 2월 28일 = 228 문제를 읽자마자 그리디일거같았지만 구현하는데 시간이 꽤 걸렸다. 코드 #include #include using namespace std; pair arr[100005]; int main() {..