👨💻 문제
무게와 가치가 정해진 보석들을
최대 무게가 정해진 가방들에
하나씩 집어넣어 최대 가치를 구하는 문제
✍️ 풀이
가치가 높은 보석부터 넣을 수 있는 가장 작은 가방에 넣으면 된다.
하지만 넣을 수 있는 가장 작은 가방을 찾는 것이 문제였다.
- 선형 탐색 : 시간 초과
- 이분 탐색 : 탐색은 빠르지만 사용한 가방을 제외하는 것이 오래 걸림
- 연결 리스트 : 사용한 가방을 제외하는 것은 빠르지만 탐색이 오래 걸림
이분 탐색과 연결 리스트의 장점을 모두 가진 세그먼트 트리를 활용하였다.
🍒 세그먼트 트리
가방의 최대 무게를 세그먼트 트리로 구성하여 현재 넣을 수 있는 최소값과 최대값을 저장한다.
ex) 가방의 최대 무게 : 1, 2, 4, 10
( 1,10)
( 1, 2) ( 4,10)
( 1, 1) ( 2, 2) ( 4, 4) (10,10) 무게가 3인 보석을 집어넣으면 최대 무게가 4인 가방을 사용할 것이다.
루트 노드는 모든 가방 가용량의 최소값과 최대값을 가지기 때문에,
넣으려는 보석이 들어갈 수 있는지 없는지 바로 확인할 수 있다.
넣을 수 있다면 좌우 자식 노드의 값들을 비교하여 알맞는 가방을 찾는다.
최대 무게가 4인 가방을 사용하면 트리를 아래와 같이 재구성한다.
( 1,10)
( 1, 2) (10,10)
( 1, 1) ( 2, 2) ( , ) (10,10) 예시
7 4
1 1
5 2
2 3
10 4
7 3
3 5
1 5
10
2
4
1
( 1,10)
( 1, 2) ( 4,10)
( 1, 1) ( 2, 2) ( 4, 4) (10,10)
weight: 3, price: 5
( 1,10)
( 1, 2) (10,10)
( 1, 1) ( 2, 2) ( , ) (10,10)
weight: 1, price: 5
( 2,10)
( 2, 2) (10,10)
( , ) ( 2, 2) ( , ) (10,10)
weight: 10, price: 4
( 2, 2)
( 2, 2) ( , )
( , ) ( 2, 2) ( , ) ( , )
weight: 7, price: 3
weight: 2, price: 3
( , )
( , ) ( , )
( , ) ( , ) ( , ) ( , )
17📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _1202 {
private static int jewelCnt;
private static int bagCnt;
private static class Jewel {
int weight, price;
public Jewel(int weight, int price) {
this.weight = weight;
this.price = price;
}
}
private static PriorityQueue<Jewel> jewels = new PriorityQueue<>((a, b) -> b.price - a.price);
private static int[] bags;
private static class SegmentNode {
int min, max;
}
private static int segmentTreeSize;
private static SegmentNode[] bagsSegmentTree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
jewelCnt = Integer.parseInt(st.nextToken());
bagCnt = Integer.parseInt(st.nextToken());
// input
for (int i=0; i<jewelCnt; i++) {
st = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());
jewels.add(new Jewel(weight, price));
}
bags = new int[bagCnt];
for (int i=0; i<bagCnt; i++) {
st = new StringTokenizer(br.readLine());
bags[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(bags);
// init segment tree
segmentTreeSize = 1;
while (segmentTreeSize < bags.length) {
segmentTreeSize *= 2;
}
segmentTreeSize *= 2;
bagsSegmentTree = new SegmentNode[segmentTreeSize];
// fill bag size
for (int i=0; i<bagCnt; i++) {
int idx = segmentTreeSize/2 + i;
bagsSegmentTree[idx] = new SegmentNode();
bagsSegmentTree[idx].min = bags[i];
bagsSegmentTree[idx].max = bags[i];
}
// fill tree
for (int i=segmentTreeSize/2 - 1; i>=1; i--) {
bagsSegmentTree[i] = new SegmentNode();
updateNode(i);
}
// printTree();
// fill jewel
int filledBagCnt = 0;
long entirePrice = 0;
loop: while (!jewels.isEmpty() && filledBagCnt < bagCnt) {
Jewel jewel = jewels.poll();
// System.out.printf("\nweight: %d, price: %d\n", jewel.weight, jewel.price);
// 넣을 수 있는 가장 작은 가방에 삽입
int i = 1;
while (true) {
SegmentNode cur = bagsSegmentTree[i];
// 넣을 수 있는 가방이 없음
if (cur.max < jewel.weight) {
// 해당 보석 탈락
continue loop;
}
// 가방에 도달
if (i >= segmentTreeSize/2) {
bagsSegmentTree[i] = null;
filledBagCnt++;
entirePrice += jewel.price;
// 트리 수정
i /= 2;
while (i >= 1) {
updateNode(i);
i /= 2;
}
// printTree();
continue loop;
}
int leftIdx = i * 2;
int rightIdx = i * 2 + 1;
SegmentNode left = bagsSegmentTree[leftIdx];
SegmentNode right = bagsSegmentTree[rightIdx];
if (left == null) {
i = rightIdx;
}
else if (right == null) {
i = leftIdx;
}
else if (left.max >= jewel.weight) {
// 더 작은 가방에 넣는 게 우선
i = leftIdx;
}
else {
// 안 되면 큰 곳에
i = rightIdx;
}
}
}
System.out.println(entirePrice);
}
private static void updateNode(int i) {
SegmentNode left = bagsSegmentTree[i*2];
SegmentNode right = bagsSegmentTree[i*2+1];
if (left == null && right == null) {
bagsSegmentTree[i] = null;
}
else if (left == null) {
bagsSegmentTree[i] = right;
}
else if (right == null) {
bagsSegmentTree[i] = left;
}
else {
bagsSegmentTree[i].min = Math.min(left.min, right.min);
bagsSegmentTree[i].max = Math.max(left.max, right.max);
}
}
// private static void printTree() {
// int from = 1;
// int length = 1;
// while (true) {
// for (int i=from; i<from + length; i++) {
// int spaceCnt = (segmentTreeSize / (from + length) - 1) * 4;
// System.out.print(" ".repeat(spaceCnt));
// System.out.printf(
// "(%s,%s) ",
// bagsSegmentTree[i] == null ? " " : String.format("%2d", bagsSegmentTree[i].min),
// bagsSegmentTree[i] == null ? " " : String.format("%2d", bagsSegmentTree[i].max)
// );
// System.out.print(" ".repeat(spaceCnt));
// }
// System.out.println();
// from = from + length;
// length *= 2;
// if (from >= segmentTreeSize) {
// break;
// }
// }
// }
}
입니다.