https://www.acmicpc.net/problem/2258
2258번: 정육점
첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는
www.acmicpc.net
사실 그저께부터 풀어보려 했으나 번번히 실패하는 문제입니다.
정육점에는 여러 고기 덩어리가 있고, 각 고기 덩어리는 무게와 가격이 천차만별입니다.
은혜는 본인이 필요로 하는 양의 고기를 사면 됩니다.
단, 가격이 더 싸다면 필요한 양보다 더 많은 고기를 살 수도 있습니다.
또한 자신이 구매한 고기보다 싼 고기들은 추가 지불 없이 얼마든지 구매할 수 있습니다.
이 때 은혜가 원하는 양의 고기를 구매하기 위한 최소 비용을 계산해야 합니다.
여태까지 제가 구현한 방식은 다음과 같습니다.
1. 무게합이 필요한 무게보다 작은지 비교한다.
2. 1의 결과가 참일 경우, 최소 비용의 무게와 현재 무게가 동일한지 비교한다.
3. 2의 결과가 참일 경우, 최소 비용과 현재 비용을 비교하여 더 작은 것을 저장한다.
4. 2의 결과가 거짓일 경우, 최소 비용과 그 무게를 현재 비용과 무게로 저장한다.
5. 1의 결과가 거짓일 경우, 최소 비용을 현재 무게와 비교하여 더 작은 것을 저장한다.
6. 무게합이 요구치보다 작을 경우 -1을, 클 경우 최소 비용을 출력한다.
하지만 9%를 넘어가는 정도에서 정답을 맞추지 못하고 실패해버립니다.
오늘은 이쯤에서 멈추고 내일 다시 풀어보겠습니다.
'개발일지 > Algorithm' 카테고리의 다른 글
| 20.07.15 개발일지 - 정육점(fail) (0) | 2020.07.15 |
|---|---|
| 20.07.13 개발일지 - 정육점(cont) (0) | 2020.07.13 |
| 20.06.27 개발일지 - 謎紛芥索紀 (Large) (0) | 2020.06.27 |
| 20.06.27 개발일지 - Pizza Boxes (0) | 2020.06.27 |
| 20.06.27 개발일지 - Q-인덱스 (0) | 2020.06.27 |