[C++] 백준 11508번 2+1 세일

1. 문제이해

11508번: 2+1 세일 (acmicpc.net)

11508번: 2+1 세일

 

재현이가 유제품을 살 때, 3개를 한꺼번에 산다면 그 중 가장 싼 유제품은 무료로 받게된다.

재현이가 사는 유제품의 개수(N)와 각 유제품의 가격이 차례로 주어질때,

재현이가 유제품을 사는 최소비용을 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

재현이가 유제품을 3개씩 산다면, 그 중 가장 싼 유제품은 무료이다.

그렇다면 당연히, 5개의 유제품을 살 때, 3, 2개로 나누어 사는게 이득이다.

또한, 3개로 묶인 유제품 중 가장 싼 제품이 무료이기 때문에,

가장 비싼 가격의 제품들을 묶어 그 중 싼 가격을 지불하지 않는 것이 이득이다.

 

예를 들어, 각각 9, 7, 5, 3 원인 유제품이 있을 때,

(9, 7, 5) (3) 으로 사서, 5원인 제품을 할인받아 사면, 총 16+3 = 19원이 든다.

반면, (3, 7, 5) (9) 로 사면, 3원인 제품을 할인받아, 총 12 + 9 = 21원이 든다.

 

이렇듯, 비싼 가격의 제품들을 차례로 묶어 그 중 그나마 싼 것을 지불하지 않는 것이 가장 이득이다.

즉, 이를 코드로 구현하면, 내림차순으로 정렬 후, 3번째 값들을 빼고 더해주면 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int dairy_product[100000];

// 내림차순
bool DESC(int a, int b) {
	return a > b;
}

int main() {
	int N;
	int sum = 0;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> dairy_product[i];
	}

	// 내림차순으로 정렬
	sort(dairy_product, dairy_product + N, DESC);
	
	for (int i = 0; i < N; i++) {

		// 3개씩 묶은 것 중 가장 작은 값 (3번째 값, 배열이므로 i+1)
		if ((i + 1) % 3 == 0) {
			continue;	// 계산하지 않음
		}
		else {
			sum += dairy_product[i];
		}
	}

	cout << sum;

	return 0;
}

위처럼, 유제품의 개수와 각각의 가격을 입력받아 배열(dairy_product[i])에 저장한 후,

해당 배열을 내림차순으로 정렬해주었다.

내림차순으로 정렬한 이후에는, 2. 문제풀이에서 언급했듯,

3개씩 묶은 값 중 가장 작은 값(3번째 값)을 제외한 나머지값들을 차례로 더해주면 된다.

 

 

---

그리디문제 위주로 문제를 푸는 연습을 하는 중이다.

기분 탓인지는 몰라도 다른 문제들보다 그리디문제는 이해하기가 조금 힘든 것 같기도하다..😥

차츰 풀면 나아지겠지..? 🙄