[Baekjoon/C++] 11508번 - 2+1 세일

[백준] Baekjoon Online Judge

문제로 이동

 

문제

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

 

입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

 

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.

 

---

예제 입력	예제 출력
4 3 2 3 2	8
6 6 4 5 5 5 5	21

---

풀이

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001];

bool compare(int a, int b);
int sale(int N, int s);

bool compare(int a, int b) {
	return a > b;
}

// 할인 받아 무료로 지불하는 것들의 가격 빼기
int sale(int N, int s) {
	int sum = s;

	for (int i = 2; i < N; i += 3)
		sum -= arr[i];

	return sum;
}

int main() {
	int N, sum = 0;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
		sum += arr[i];
	}

	sort(arr, arr + N, compare);

	printf("%d\n", sale(N, sum));

	return 0;
}

입력 받은 유제품의 가격들을 arr[]에 저장한 뒤 이를 sum에 더해주었다. 그리고 compare 함수를 정의해서 arr[]를 내림차순으로 정렬했다.

 

// 할인 받아 무료로 지불하는 것들의 가격 빼기
int sale(int N, int s) {
	int sum = s;

	for (int i = 2; i < N; i += 3)
		sum -= arr[i];

	return sum;
}

내림차순으로 정렬한 가격들의 2번째, 5번째, 8번째... 즉, 2 + 3 * n의 자리에 있는 가격은 할인 받아 돈을 내지 않아도 되기에 이를 sum에서 빼야 한다. 그리고 이렇게 할인 받아야 최소 비용을 구할 수 있다.