알고리즘/그리디

[백준] 1202 보석 도둑 (그리디) - Java

2023. 5. 10. 17:51
목차
  1. 문제 설명
  2. 입력
  3. 출력
  4. 접근법
  5. 문제 풀이
  6. 시간초과 (가장 비싼 보석을 가장 가벼운 가방에 넣는 방식) - O(NM)
  7. 통과

 

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

 

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

접근법

처음 접근 : 가장 비싼 보석을 가장 가벼운 가방에 넣는 방식

  • 보석의 무게, 보석의 가격으로 이루어진 Jewel 클래스를 보석의 가격 내림차순으로 우선순위 큐에 넣음
  • 가방의 무게를 오름차순으로 정렬
  • 우선순위 큐에서 하나씩 꺼내 for문을 돌며 보석이 들어갈 수 있는 가장 가벼운 가방 찾음
  • 시간복잡도 O(NM) → 시간초과

 

두번째 접근

  • 보석의 정보와 가방의 무게를 각각 리스트에 저장
  • 보석리스트 - 보석 무게를 기준으로 오름차순 정렬
  • 가방리스트 - 오름차순 정렬
  • 가방리스트 탐색(가방 무게가 작은것부터) : 해당 가방에 담을 수 있는 모든 보석의 가격을 우선순위 큐에 넣음
  • 우선순위 큐(내림차순 기준)에서 값을 꺼내면 해당 가방에 넣을 수 있는 가장 비싼 보석
  • 가방 1개당 우선순위 큐에서 값을 1개씩 꺼내서 가격 합에 더해줌

 

예제

 

우선순위 큐에 가격이 높은 순으로 저장

→ 가방 1개마다 우선순위 큐에서 값을 1개씩 꺼내서 sum에 더해줌

→ sum = 65

 

sum = 65+100 = 165

 

sum = 165 + 99 = 264

 

 

문제 풀이

시간초과 (가장 비싼 보석을 가장 가벼운 가방에 넣는 방식) - O(NM)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static PriorityQueue<Jewel> pq;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        pq = new PriorityQueue<>();
        List<Integer> maxWeightList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.valueOf(st.nextToken());
            int price = Integer.valueOf(st.nextToken());
            pq.offer(new Jewel(weight, price));
        }

        for (int i = 0; i < K; i++) {
            maxWeightList.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(maxWeightList);

        int sum = 0;

        while (!pq.isEmpty()){
            Jewel jewel = pq.poll();
            int weight = jewel.weight;
            int price = jewel.price;

            for (int i = 0; i < maxWeightList.size(); i++) {
                int maxWeight = maxWeightList.get(i);
                if(maxWeight >= weight){
                    sum += price;
                    maxWeightList.remove(i);
                    break;
                }
            }
        }

        System.out.println(sum);

    }
    static class Jewel implements Comparable<Jewel> {
        private int weight;
        private int price;

        public Jewel(int weight, int price){
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Jewel o) {
            return Integer.compare(o.price, this.price);
        }
    }
}

 

통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        List<Jewel> jewelList = new ArrayList<>();
        List<Integer> bagWeight = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.valueOf(st.nextToken());
            int price = Integer.valueOf(st.nextToken());
            jewelList.add(new Jewel(weight, price));
        }

        for (int i = 0; i < K; i++) {
            bagWeight.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(jewelList);
        Collections.sort(bagWeight);

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        long sum = 0;
        int idx = 0;
        for (int i = 0; i < bagWeight.size(); i++) {
            while (idx < N && jewelList.get(idx).weight <= bagWeight.get(i)){
                pq.offer(jewelList.get(idx).price);
                idx++;
            }
            if(!pq.isEmpty()){
                sum += pq.poll();
            }
        }

        System.out.println(sum);

    }
    static class Jewel implements Comparable<Jewel> {
        private int weight;
        private int price;

        public Jewel(int weight, int price){
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Jewel o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
}

 

저작자표시 (새창열림)

'알고리즘 > 그리디' 카테고리의 다른 글

[백준] 11047 동전 0 (그리디) - Java  (0) 2023.05.11
[백준] 1715 카드 정렬하기 (그리디) - Java  (0) 2023.05.11
  1. 문제 설명
  2. 입력
  3. 출력
  4. 접근법
  5. 문제 풀이
  6. 시간초과 (가장 비싼 보석을 가장 가벼운 가방에 넣는 방식) - O(NM)
  7. 통과
'알고리즘/그리디' 카테고리의 다른 글
  • [백준] 11047 동전 0 (그리디) - Java
  • [백준] 1715 카드 정렬하기 (그리디) - Java
jny0
jny0
성장일기
jny0
J N Y 0
jny0
  • 분류 전체보기 (192)
    • 트러블슈팅 (6)
    • Java (22)
    • HTML, CSS , JavaScript (7)
    • MySQL, DBMS (9)
    • GIT (6)
    • 객체지향의 사실과 오해 (3)
    • 자바 ORM 표준 JPA 프로그래밍 (13)
    • 알고리즘 (114)
      • 자료구조 (59)
      • 수학 (11)
      • 정렬 (2)
      • 그리디 (3)
      • DP (4)
      • 그래프 (3)
      • 탐색 (9)
      • 재귀 (2)
      • 문자열 (9)
      • 기타 (12)
    • CS (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • 누적합
  • 백준
  • 스택
  • 프로그래머스
  • 구현
  • JPA
  • Java
  • JS
  • db
  • 그리디
  • 자료구조
  • DP
  • MySQL
  • method
  • git
  • 알고리즘
  • 영상후기
  • codeup
  • 투포인터
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.
jny0
[백준] 1202 보석 도둑 (그리디) - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.