[백준/Baekjoon] 1202 보석 도둑 C++ :: Greedy

2023. 9. 13. 03:26· Algorithm/Beakjoon
목차
  1. 1. Logic
  2. 2. Code
  3. 3. Feedback
728x90
반응형

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

 

1202번: 보석 도둑

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

www.acmicpc.net


1. Logic

multiset 해설

1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다.

2. 가방의 무게를 입력받아 multiset으로 넣는다.

3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다

 

vector 해설

1. 보석과 가방을 벡터에 입력 받아준 후 오름차순으로 정렬한다.

2. 보석의 무게와 가방의 용량을 비교하여 가방에 들어갈 수 있는 무게를 가진 보석들만 우선순위 큐에 넣어준다.

3. 그 중에서 가장 높은 가치를 가진 보석의 값만 더해주고 pq에서 pop()

 

처음에는 벡터와 우선순위 큐에 값을 넣고 모두 순회하며 그리디한 방식으로 접근을 했지만 시간초과가 났다. 그래서 vector의 순회가 문제인 것 같아 시간복잡도가 O(logN)을 가지는 자료구조인 Multiset 을 활용하여 풀었다. multiset 또한 iterator을 사용하여 처음부터 끝까지 돌며 확인했지만 또 시간초과가 떠서 값을 찾는 방식을 multiset의 O(logN)의 이진탐색을 활용한 multiset의 lower_bound를 사용하니 정답 처리가 됐다. 

자료구조의 문제인줄 알고 다시한번 vector의 lower_bound로 구현해봤더니 시간초과가 떴다.

결론적으로 자료구조와 lower_bound 둘다 잘 맞아 떨어져야 하는 문제인 것같다.

 

코드는 multiset 순회, multiset - lower_bound, vector 활용, vector - lower_bound 4가지 버전 다 올려놓을 것이다.

 

 


2. Code

multiset - lower_bound 풀이 - 정답

#include<bits/stdc++.h>
#include <queue>
#include <set>
using namespace std;
priority_queue<pair<int, int>> pq;
multiset<int> bag;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n, k;
long long answer = 0;
cin >> n >> k;
for(int i = 0; i < n; i++) {
int weight, value;
cin >> weight >> value;
pq.push({value, weight});
}
for(int i = 0; i < k; i++) {
int size;
cin >> size;
bag.insert(size);
}
while(!bag.empty()) {
if(pq.empty()) break;
//multiset<int>::iterator iter = bag.lower_bound(pq.top().second);
multiset<int>::iterator iter;
bool check = false;
for(iter = bag.begin(); iter != bag.end(); iter++){
if(*iter >= pq.top().second) {
check = true;
bag.erase(iter);
answer += pq.top().first;
pq.pop();
break;
}
}
if(!check) {
pq.pop();
}
}
cout << answer;
}

multiset 순회 - 시간 초과

 

#include<bits/stdc++.h>
#include <queue>
#include <set>
using namespace std;
priority_queue<pair<int, int>> pq;
multiset<int> bag;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n, k;
long long answer = 0;
cin >> n >> k;
for(int i = 0; i < n; i++) {
int weight, value;
cin >> weight >> value;
pq.push({value, weight});
}
for(int i = 0; i < k; i++) {
int size;
cin >> size;
bag.insert(size);
}
while(!bag.empty()) {
if(pq.empty()) break;
//multiset<int>::iterator iter = bag.lower_bound(pq.top().second);
multiset<int>::iterator iter;
bool check = false;
for(iter = bag.begin(); iter != bag.end(); iter++){
if(*iter >= pq.top().second) {
check = true;
bag.erase(iter);
answer += pq.top().first;
pq.pop();
break;
}
}
if(!check) {
pq.pop();
}
}
cout << answer;
}

벡터를 활용한 풀이 - 정답

#include<bits/stdc++.h>
#include <queue>
using namespace std;
int n, k;
vector<int> bag;
vector<pair<int, int>> jems;
priority_queue<int> pq;
long long solve() {
int idx = 0;
long long sum = 0;
for(int i = 0; i < k; i++) {
// 가방에 들어갈 수 있는 무게를 가진 보석들을 전부 넣기
while(idx < n && bag[i] >= jems[idx].first) {
pq.push(jems[idx].second);
idx++;
}
if(!pq.empty()) {
sum += pq.top();
pq.pop();
}
}
return sum;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 0; i < n; i++) {
int weight, value;
cin >> weight >> value;
jems.push_back({weight, value});
}
for(int i = 0; i < k; i++) {
int a;
cin >> a;
bag.push_back(a);
}
sort(jems.begin(), jems.end());
sort(bag.begin(), bag.end());
cout << solve();
}

vector - lower_bound - 시간 초과

 

#include<bits/stdc++.h>
#include <queue>
#include <set>
using namespace std;
priority_queue<pair<int, int>> pq;
vector<int> bag;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n, k;
long long answer = 0;
cin >> n >> k;
for(int i = 0; i < n; i++) {
int weight, value;
cin >> weight >> value;
pq.push({value, weight});
}
for(int i = 0; i < k; i++) {
int size;
cin >> size;
bag.push_back(size);
}
sort(bag.begin(), bag.end());
while(!bag.empty()) {
if(pq.empty()) break;
vector<int>::iterator iter = lower_bound(bag.begin(), bag.end(), pq.top().second);
if(iter == bag.end()) {
pq.pop();
continue;
}
else {
bag.erase(iter);
answer += pq.top().first;
pq.pop();
}
}
cout << answer;
}

3. Feedback

처음에 시간초과를 받은 후 다른 자료구조를 생각해보다가 나름 빠른시간안에 multiset을 생각해낸 것 만으로도 만족스러웠다. 그리고 multiset과 vector의 iterator을 사용할 줄 몰라 엄청 찾아보면서 풀었다. 결국 구글링을 해보면서 생각해낸 4가지 풀이 모두 정답을 받진 못했지만 이건 문제의 조건때문이기 때문에 구현을 완료해서 굉장히 뿌듯햇다. 그리고 처음으로 집요하게 파고들어 자료구조, STL등 깊게 찾아보며 풀이한 첫번째 문제인 것 같다. 알고리즘 공부에 대해 느낀점을 만들어 준 문제인 것 같아 쉽게 안잊힐 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐
728x90
반응형

'Algorithm > Beakjoon' 카테고리의 다른 글

[백준/Baekjoon] 2212 센서 C++ :: Greedy  (0) 2023.09.14
[백준/Baekjoon] 2812 크게 만들기 C++ :: Data Structure & Greedy  (0) 2023.09.13
[백준/Baekjoon] 1339 단어 수학 C++ :: Greedy  (0) 2023.09.12
[백준/Baekjoon] 1715 카드 정렬하기 C++ :: Greedy  (0) 2023.09.12
[백준/Baekjoon] 7490 0 만들기 C++ :: Recursion & Back Tracking  (0) 2023.09.12
  1. 1. Logic
  2. 2. Code
  3. 3. Feedback
'Algorithm/Beakjoon' 카테고리의 다른 글
  • [백준/Baekjoon] 2212 센서 C++ :: Greedy
  • [백준/Baekjoon] 2812 크게 만들기 C++ :: Data Structure & Greedy
  • [백준/Baekjoon] 1339 단어 수학 C++ :: Greedy
  • [백준/Baekjoon] 1715 카드 정렬하기 C++ :: Greedy
보글보글소다
보글보글소다
반응형
보글보글소다
Conquer Mind, Conquer All
보글보글소다
전체
오늘
어제
  • 분류 전체보기
    • Algorithm
      • Beakjoon
      • Programmers
    • Frontend
      • React.js
      • JavaScript
    • Backend
      • Java
      • Spring
      • Node.js
    • Design Pattern
    • Computer Science
      • Algorithm
      • 컴퓨터구조
      • 운영체제
      • 네트워크
      • 데이터베이스
      • 자료구조
    • Projects
      • 식단 짜주는 웹
    • 정보보호병
      • Study In military
      • 정보보호병
    • 인공지능
      • 논문 리뷰

블로그 메뉴

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

공지사항

인기 글

태그

  • 자료구조
  • Algorithm
  • 그래프
  • 스프링
  • 구현
  • 이분탐색
  • 알고리즘 풀이
  • 동적계획법
  • spring
  • 코딩테스트
  • BaekJoon
  • 백준 풀이
  • 백준
  • DP
  • 프로그래머스
  • Programmers
  • BFS
  • 운영체제
  • 백엔드
  • 알고리즘

최근 댓글

최근 글

250x250
hELLO · Designed By 정상우.v4.2.2
보글보글소다
[백준/Baekjoon] 1202 보석 도둑 C++ :: Greedy
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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