[백준 2258번] 정육점 - java

문제 설명

1. 고기의 수 N과 필요한 고기의 무게 M이 주어진다.

2. 고기의 무게과 가격이 주어진다.

3. 구매한 고기보다 싼 고기는 공짜로 준다.

4. 가장 적은 돈을 들여서 고기를 사는 방법을 구하면 된다.

 

풀이 과정

 1. 이거 실버1인거 보고 방심하고 풀었는데...... 진짜 엄청 헤맸다. 쉽게 보고 풀면 안되는 함정문제이다.

 2. 구매한 고기보다 싸면 공짜로 주니까 그냥 가격순으로 오름차순 하면서 더해주면 되겠지? 했는데 싼 고기라는게 굉장히 중요하다.

 3. 즉, 구매한 고기랑 같은 가격의 고기는 공짜로 안준다!!!

 4. 이를 생각하고 풀이과정을 도출해보자

---

A. 우선순위 큐를 구현하여 가격이 같으면 무게는 내림차순으로 가게끔 <가격순(오름차순), 무게순(내림차순)> 으로 만들어 준다. 

B. 이 우선순위 큐가 끝날 때 까지 무게를 구해서 답이 나오면 boolean값을 true로 하고, 아니면 false로 유지하면서 하나씩 꺼내준다.

C. B단계에서 내용을 꺼낼때 일단 그곳의 가격을 저장해 주고, 다음번 poll단계에서의 가격과 비교해 준다.

C-1. 이전 가격과 현재 가격이 다른 경우 -> 같은 가격만큼 더해진 저장값을 하나 만들어두고, 이 값을 가격만큼 더해준다.

C-2. 이전 가격과 현재 가격이 같은 경우 -> 가격이 올라갔으니 구매해줄 값은 현재가격이 되고, C-1에서의 저장값을 초기화한다.

그리고 전체 구매한 무게를 더해준다.

D. C단계가 무엇이 되었든, C를 통해 얻어진 무게와 원하는 무게를 비교하여 원하는 것보다 이 무게가 많으면 답은 존재한다. boolean을 true로 해 주고, answer을 C에서의 저장값+구매값의 최소로 해준다.

 

-> 말로 설명하면 헷갈릴 수 있는데, 이런 경우가 있다고 하자

무게	가격
3	3
2	3
3	4

원하는 고기의 무게가 5kg이라면, 얼마를 써야할까?

ㄱ. 아무 생각없이 우선순위 큐를 쓴다면 3의 가격으로 구할 수 있다고 할 것이다.

ㄴ. 가격3의 물건들을 일단 구해두고(3+3), 이후에 다시 가격4로 물건을 구하는 경우를 세면 더 싸게 구할 수 있다.

---

 3. 이런 식으로 하면 되는데, 함정에 빠지기 쉽고 또 해결법을 생각해 냈다고 해도 생각보다 구현이 쉽지 않았다. 대체 왜 이게 실버1인지...

코드