[백준 / BOJ] 1202 보석 도둑 - (유니온 파인드, 이분탐색)

문제

출처 : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

상덕이는 보석을 털기로 결심했다.

보석점에 총 N개의 보석이 있고, 각 보석은 M의 무게, V의 가격을 갖고있다.

상덕이는 K개의 가방을 갖고있고, 각 가방에는 최대 Ci무게의 보석을 담을수있다. 이때, 각 가방에는 최대 한개의 보석만 담을수있다.

 

상덕이가 홈칠수있는 보석의 최대 가격을 출력하는 문제다.

 

풀이

보석의 수 N과 가방의 수 K가 각각 최대 30만까지 갈수있으므로, 완전탐색으로 풀경우 O(NK)시간복잡도를 갖게되어 시간초과가 나온다.

 

시간초과를 해결하기위해, 이분탐색과 유니온파인드를 이용해 문제를 풀었다.

 

상덕이가 보석의 가격을 최대로 훔칠려면 비싼 보석먼저 훔치는게 항상 이득이므로, 보석을 {가격, 무게}로 정렬해줬다.

 

상덕이가 갖고있는 가방중, 현재 보석(가격이 높은 보석먼저 가방에 넣을수있는지 확인한다)의 무게 보다 크거나 같은 가방을 찾아주는데, 이를 완전탐색으로 찾아줄려하면, O(K)가 되므로, 상덕이의 가방을 정렬후 이분탐색으로 찾아줘 O(logK)로 시간을 줄여준다.

 

선택가능한 가방을 찾는 과정중 이미 선택한 가방을 선택하지 못하게 처리하는것이 문제였는데, 처음 생각한 로직은

- 반환값이 이미 선택한 가방이라면 -> left = 선택한 가방위치 +1 right = 상덕이가 갖고있는 가방의 수 로 잡고 다시 이분탐색을 반복하는것이였다.

이렇게 하면, 최악의경우 left+1 -> left+1+1 -> left+1+1+1... 와 같이 반복하고 O(KlogK)로 오히려 시간이 길어질수있어 시간초과를 피하지 못한다.

 

이를 해결하기 위해 유니온 파인드를 사용했다.

- 반환값이 이미 선택한 가방이라면 -> left = unionFind(이분탐색(선택한 가방위치+1))와 같이 경로를 압축해 넘겨준다.

(가방의 최대 무게가 1억까지 가므로 배열로는 유니온파인드를 구현하지못하고, map을 이용해 구현했다.)

left값을 빠르게 압축하는것이 중요했던 문제다. 

 

1. {무게}를 담을수있는 가방의 수를 표현하는 map을 선언한다. map<가방의 무게, 무게를 담을수 있는 가방의 수>bagCnt

- 만약 map[가방의 무게] = 0 이라면, 해당 무게를 담을 수있는 가방은 0개 이므로, 다음 위치를 찾아준다.

 

2. 유니온파인드를 구현하기위해, 부모 idx를 표현하는 map을 선언한다. map<자식idx, 부모idx>uni

- 만약 부모가 없다면 자기자신을 가리키게 구현해놓았다. uni[1] = 1 (bagCnt[1] == 0 이며, 1 다음 가방이 4라면, uni[1] = 4)

 

i번째 보석의 무게를 Ai라 하자.

가격이 높은 보석먼저 가방에 넣을수있는지 확인하며 만약 가방에 넣을수있다면(uni[Ai] == Ai && bagCnt[Ai] > 0), 가방에 넣고, 

bagCnt[Ai]--; 를 해준다.

해당하는 가방은 있지만, bagCnt[Ai] == 0 이라면, 가방에 넣을 수 없는것 이므로(해당 무게를 담을수있는 가방을 이미 다 사용함) uni[Ai] = unionFind(이분탐색(Ai+1))로 다음에 Ai를 입력받은경우 바로 선택할 수 있는 최소가방을 반환해주도록 구현해놓는다.

 

map에서 원하는 자료를 찾는데 logN번 반복하고, 유니온파인드를 업데이트할때마다 logN번 반복하므로 정확한 시간복잡도를 계산하기 어렵지만, 약, 

1. 모든 보석을 순회 : N

2. 유니온 파인드 : log(N+K)

3. bagCnt탐색 : log(N+K)

번 반복하여

O(N*(log(N+K))^2)번 반복으로 답을 구할 수 있다.

(map을 탐색할때마다 log번 반복하므로 주소 연산자로 중복호출을 제거해서 걸리는 시간을 최소화 하도록하자)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1202%20%EB%B3%B4%EC%84%9D%20%EB%8F%84%EB%91%91/main.cpp

devxb/JJUNalgo