[Softeer] 금고털이 - Java

https://softeer.ai/practice/info.do?idx=1&eid=395&sw_prbl_sbms_sn=213446 

Softeer

---

1. 문제

배낭에 들어갈 수 있는 최대 무게 W, 귀금속 종류 개수 turn을 입력으로 받는다.

배낭을 채울 수 있는 가장 비싼 가격을 구해 출력한다.

2. 풀이

간단한 구현 문제이다.

1. 가격 높은 순으로 정렬하는 pq를 사용한다.

2. pq가 비지 않을 때까지 반복하며

- 다음 귀금속의 무게가 남은 무게보다 클 경우, ans 갱신, 반복문 break;

- 다음 귀금속의 무게가 남은 무게보다 작을 경우, ans 갱신, 남은 무게 갱신

3. 코드

import java.util.*;
import java.io.*;


public class Main
{
    static PriorityQueue<Node> pq = new PriorityQueue<> ((o1,o2)-> (o2.price-o1.price));
    static int W, turn, ans;

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        turn = Integer.parseInt(st.nextToken());

        for (int i=0; i<turn; i++) {
            st = new StringTokenizer(br.readLine());
            pq.offer(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        //입력 끝

        solution();
        System.out.println(ans);
    }

    static void solution() {
        while (!pq.isEmpty()) {
            Node n = pq.poll();
            if (n.weight >= W) {
                ans += W * n.price;
                break;
            }
            else {
                ans += n.weight * n.price;
                W -= n.weight;
            }
        }
    }

    static class Node {
        int weight, price;
        Node(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
    }
}

4. 사담

갈 때까지 하자 누가이기나 해보자