Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 백준
- 브루트포스
- 유니티
- 수학
- 알고리즘
- 백트래킹
- 재귀
- BFS
- 문자열
- 시뮬레이션
- XR Interaction Toolkit
- VR
- 누적 합
- 자료구조
- 유니온 파인드
- 그리디 알고리즘
- 정렬
- ue5
- c++
- DFS
- 구현
- 그래프
- 트리
- 우선순위 큐
- 다익스트라
- 투 포인터
- Unreal Engine 5
- 스택
- 다이나믹 프로그래밍
- Team Fortress 2
Archives
- Today
- Total
1일1알
백준 2258번 정육점 C++ 본문
https://www.acmicpc.net/problem/2258
어떤 고기를 샀을 때 그 가격보다 싼 고기는 무료로 얻을 수 있다.
고기의 가격은 오름차순, 가격이 같을때는 무게를 내림차순으로 정렬한다.
정렬된 순서로 고기의 무게를 더하다가 m보다 크거다 같게 되면 지금 고기의 가격과 같은 가격의 고기가 앞에 있는 만큼 더해서 가격을 측정하고, 측정한 값과 지금 고기보다 비싼 가격의 고기의 가격 중 싼 가격을 고른다. (지금보다 비싼 가격의 고기를 고른다면 전의 고기는 무료로 얻을 수 있기 때문)
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int n, m;
struct MeatInfo {
int weight;
int price;
bool operator<(const MeatInfo& other) {
if (price == other.price) return weight > other.weight;
return price < other.price;
}
};
vector<MeatInfo> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int weight, price;
cin >> weight >> price;
v.push_back({ weight,price });
}
sort(v.begin(), v.end());
int index = 0;
int lastPrice = 0;
int sum = 0;
int ans = -1;
int sameCnt = 1;
for (index = 0; index < n; index++) {
sum += v[index].weight;
if (lastPrice == v[index].price) {
sameCnt++;
}
else {
sameCnt = 1;
}
if (sum >= m) {
ans = v[index].price * sameCnt;
break;
}
lastPrice = v[index].price;
}
for (int i = index + 1; i < n; i++) {
if (v[i].price > lastPrice) {
ans = min(ans, v[i].price);
break;
}
}
cout << ans;
}
'알고리즘' 카테고리의 다른 글
백준 2194번 유닛 이동시키기 C++ (0) | 2023.02.09 |
---|---|
백준 1911번 흙길 보수하기 C++ (0) | 2023.02.08 |
백준 1735번 분수 합 C++ (0) | 2023.02.06 |
백준 14494번 다이나믹이 뭐에요? C++ (0) | 2023.02.05 |
백준 13901번 로봇 C++ (0) | 2023.02.04 |