[백준 1202번] 보석 도둑

문제 링크: www.acmicpc.net/problem/1202

1202번: 보석 도둑

대표적인 Greedy Method를 이용하는 문제입니다.

제가 접근한 방법은,

• 가지고 있는 보석을 값이 비싼 순서대로 정렬한다.
• 비싼 보석부터 차례로 가방에 넣습니다.
• 더 담을 수 있는 가방이 없으면, 프로그램을 종료하고, 가방에 넣은 보석의 총 값어치를 출력합니다.

이를 위하여 보석의 정보를 기록하기 위하여 <long long, long long> 형식의 pair라는 타입을 만들고,

priority queue MV를 만들어, pair 타입의 데이터를 enqueue 하였습니다.

이 때, 보석의 값어치 순으로 데이터를 사용해야 하므로, <V, M> 순서대로 push 하였습니다.

 

이어서 가방의 경우,

이번에 저에게는 조금 생소한 set라는 자료구조를 활용하였습니다.

구체적으로는 multiset을 활용하였는데, 

가방의 번호는 중복되지 않고, set을 사용하면 굳이 정렬을 할 필요가 없기 때문에 수행시간에서 이득을 챙길 수 있었습니다.

set에 대한 자세한 설명은 여기를 참고하였으며, multiset에 대한 설명은 여기를 참고하였습니다.

 

이후 보석을 값이 비싼 순서대로 하나씩 꺼내고 (priority queue의 top() 을 이용),

iter를 생성하고 lower bound를 이용하여 현재 보석의 무게보다 크거나 같은 키를 가진 첫 번째 iterator를 저장하였습니다.

만약 iter가 가리키는 가방의 크기와 보석의 무게가 같으면, iter의 가방을 씁니다.

그렇지 않고, iter가 끝이 아닐 경우, iter의 가방을 씁니다.

위 반복문은 가방이 다 찰 때까지 계속됩니다.

 

이후 결과를 출력합니다.

 

위 문제를 저는 처음에는 단순히 array를 사용하여 풀었으나,

array의 초기화 및 가장 큰 값의 element를 찾는 과정 등에서 시간 초과가 났습니다.

그래서 이를 해결할 수 있는 방법이 있을까 찾아보던 차에,

set을 이용하면 빠르게 풀 수 있다는 조언을 보고 set을 쓰게 되었습니다.

set을 아예 처음 접해봤기에 코드가 다소 어색하긴 합니다.

 

기존 시간초과 나는 코드:

 

 

 

*코딩 테스트 스터디 그룹을 통해 접한 문제입니다. 링크