치킨 날다

지원한 회사에서 과제를 제출하라는 연락을 받아 2주 가량 쉽니다.

어제 면접을 보고 몇가지 알아볼 것이 있어서 문제를 풀지 못했습니다.

그리고 오늘은 지원한 회사에서 과제 제출을 하라고 연락을 받았습니다.

아무래도 시간이 걸릴 것 같아 제출일까지 알고리즘 문제 풀이는 비주기적으로 진행하려 합니다.

2주 정도 걸릴 것이고, 그 사이에 여유가 되면 풀 수도 있지만 대부분은 과제에 시간을 할애할 것 같습니다.

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

사실 그저께부터 풀어보려 했으나 번번히 실패하는 문제입니다.

정육점에는 여러 고기 덩어리가 있고, 각 고기 덩어리는 무게와 가격이 천차만별입니다.

은혜는 본인이 필요로 하는 양의 고기를 사면 됩니다.

단, 가격이 더 싸다면 필요한 양보다 더 많은 고기를 살 수도 있습니다.

또한 자신이 구매한 고기보다 싼 고기들은 추가 지불 없이 얼마든지 구매할 수 있습니다.

이 때 은혜가 원하는 양의 고기를 구매하기 위한 최소 비용을 계산해야 합니다.

여태까지 제가 구현한 방식은 다음과 같습니다.

1. 무게합이 필요한 무게보다 작은지 비교한다.

2. 1의 결과가 참일 경우, 최소 비용의 무게와 현재 무게가 동일한지 비교한다.

3. 2의 결과가 참일 경우, 최소 비용과 현재 비용을 비교하여 더 작은 것을 저장한다.

4. 2의 결과가 거짓일 경우, 최소 비용과 그 무게를 현재 비용과 무게로 저장한다.

5. 1의 결과가 거짓일 경우, 최소 비용을 현재 무게와 비교하여 더 작은 것을 저장한다.

6. 무게합이 요구치보다 작을 경우 -1을, 클 경우 최소 비용을 출력한다.

하지만 9%를 넘어가는 정도에서 정답을 맞추지 못하고 실패해버립니다.

오늘은 이쯤에서 멈추고 내일 다시 풀어보겠습니다.