Softeer - 금고털이

금고털이 : https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_125927&psProblemId=395#hold

---

Problem

---

Solve

보석을 각각 비교하게된다면 시간초과가 발생하기 때문에 가방에 들어갈 보석들의 가격을 효율적으로 찾아야합니다.

처음에 생각했을때는 W이하의 무게를 가진 보석과 초과 무게를 가진 보석을 나누어 각각 우선순위 큐에 넣고 가방에 넣을 수 있는 W이하의 보석을 최대한 넣고 남는 공간을 초과 무게 보석중 가장 큰 보석을 잘라서 넣도록 구현하였습니다.

하지만 예외 케이스를 만들어보면서 (M, P) -> (50, 4), (60, 5) 인 경우 60무게를 가진 보석을 자르는게 250으로 더 효율적이였습니다.
가격이 낮더라도 많은 보석을 넣으면 더 크지 않을까 생각하였지만, (M, P) -> (40, 4), (30, 3), (60, 5)으로 보면 결국 가격이 가장 높은 보석을 잘라서 넣는게 가장 큰 가격을 얻게됩니다. (지금 생각해보면 당연해보입니다.)

그렇기 때문에 모든 보석을 우선순위에 넣고 가격을 기준으로 내림차순 정렬을 수행해줍니다.
그 후, 보석이 존재할때 보석의 무게가 W를 넘어가게되면 보석을 남는 만큼 잘라주고 얻을 수 있는 가격을 갱신하고 반복을 종료합니다. W를 넘어가지 않는다면 해당 무게에 맞게 가격을 갱신하고 다음 보석을 비교해줍니다.

//현재 가방에 넣은 보석 무게와 가격
int weight = 0;
int cost = 0;
while(!pq.isEmpty()){
	Jewerly jewerly = pq.poll();

	//가방에 들어간 보석의 무게와 현재 보석무게가 W를 넘어가게 되는 경우
	if(weight + jewerly.weight > W){
    	//가방에 넣을 수 있는 만큼 잘라서 가격을 갱신해주고 반복을 중단합니다.
		cost += (W-weight) * jewerly.cost;
		break;
	}

	//현재 보석이 가방에 들어갈수 있다면 가방에 넣은 보석의 무게와 가격을 갱신해줍니다.
	weight += jewerly.weight;
	cost += jewerly.weight * jewerly.cost;
}

---

Code

public class Main
{
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int W = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		PriorityQueue<Jewerly> pq = new PriorityQueue<>();
		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine()," ");
			int M = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());

			pq.offer(new Jewerly(M, P));
		}

		int weight = 0;
		int cost = 0;
		while(!pq.isEmpty()){
			Jewerly jewerly = pq.poll();

			if(weight + jewerly.weight > W){
				cost += (W-weight) * jewerly.cost;
				break;
			}

			weight += jewerly.weight;
			cost += jewerly.weight * jewerly.cost;
		}

		bw.write(String.valueOf(cost));
		bw.flush();
		bw.close();
	}

	static class Jewerly implements Comparable<Jewerly>{
		int weight;
		int cost;
		public Jewerly(int weight, int cost){
			this.weight = weight;
			this.cost = cost;
		}

		@Override
		public int compareTo(Jewerly o){
			return o.cost-this.cost;
		}
	}
}

---

Result

---

Reference