[Algorism/HackerRank] Greedy Florist
👉 문제 링크
✏️ 문제 요약
- 친구들에게 덤탱이 씌운 꽃 가격을 최소한의 비용으로 구매하라
- 덤탱이 공식: 한 사람이 꽃을 2개이상 사는경우, 2개부터는 1개를 더한 값으로 받는다.
ex:) [1, 2, 3] 각각의 꽃 가격일 때, 한 사람이 꽃을 사는 최소 비용은 위 수식과 같다.
제일 비싼 3원짜리 꽃을 1개 삼
그 다음 비싼 2원짜리 꽃은 이전에 3원짜리를 샀으므로 1개를 더한 값으로 구매
마지막 1원짜리를 사기전에는 2원, 3원 꽃을 산 만큼 2개를 더한 값으로 구매
💡 문제 풀이
-
최소 비용으로 구매하려면 덤탱이 없이 원래 꽃 가격으로 사야한다.
=> 모든 꽃을 1개씩은 사야하므로, 구매할 꽃의 개수보다 인원 수가 많거나 같으면 덤탱이를 당할일이 없다. -
꽃을 구매할 인원 수가 꽃 개수보다 작은 경우, 덤탱이를 최대한 줄여야한다.
=> 싼 가격에 큰 수 덤탱이를 곱해야 비용이 줄어든다. -
위 2개를 조합해 보면...
- 비싼 꽃부터 인원 수만큼 구매한다.
- 꽃을 다 구매했다면, 최소비용이다.
- 아직 더 사야할 꽃이 있다면, 모든 인원이 꽃을 샀기 때문에 덤탱이 개수가 1개씩 증가한 가격으로 꽃을 구매한다. 이 때도, 비싼 꽃부터 덤탱이 공식으로 구매한다.
- 이 내용을 반복한다.
💻 구현 코드
-
주어진 배열을 내림차순으로 정렬
-
인원 수만큼 꽃을 사보고, 꽃이 남아 있으면 덤탱이를 씌움
static int getMinimumCost(int k, int[] c) {
List<Integer> descendingList = Arrays.stream(c).boxed()
.sorted(Collections.reverseOrder())
.collect(Collectors.toList());
int minimizedCost = 0;
int multiply = 0; // 덤탱이 곱셈
for (int i = 0; i < descendingList.size(); i++) {
if (i % k == 0) {
multiply++;
}
minimizedCost += (multiply) * descendingList.get(i);
}
return minimizedCost;
}
Author And Source
이 문제에 관하여([Algorism/HackerRank] Greedy Florist), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@black-mins/AlgorismHackerRank-Greedy-Florist저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)