[Baekjoon/C++] 28062번 - 준석이의 사탕 사기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

준석이는 두 동생을 위해 사탕 가게에서 사탕을 최대한 많이 사 가려고 한다. 사탕 가게에는 N개의 사탕 묶음이 있으며 i번째 사탕 묶음에는 ai개의 사탕이 있다. 준석이는 정말 부자라 사탕 묶음을 마음껏 살 수 있다. 하지만 준석이가 사간 총 사탕의 개수가 홀수가 되면 두 동생이 사탕을 한 개라도 더 갖기 위해 서로 싸울 것이라 총 짝수 개의 사탕을 가져가려고 한다. 준석이를 위해서 최대로 가져갈 수 있는 사탕의 개수를 구해주자!

 

입력

첫째 줄에 사탕 묶음의 개수 N이 주어진다. (1 <= N <= 1000)

둘째 줄에 각각의 사탕 묶음에 담겨있는 사탕의 개수 a1, a2, ..., aN가 주어진다. (1 <= ai <= 1000) 

입력으로 주어지는 모든 수는 정수이다.

 

출력

준석이가 최대로 가져갈 수 있는 사탕의 개수를 출력한다.

사탕을 홀수 개로만 가져갈 수 있으면 0을 출력한다.

 

---

풀이

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

vector<int> holsu;

int holsuSum();

// 사탕이 홀수로 들어있는 묶음 구매하기
int holsuSum() {
	int cnt = 0;
    
    // 묶음의 개수가 홀수라면 가장 작은 묶음을 제외한다.
	for (int i = (holsu.size() % 2 == 1); i < holsu.size(); i++) cnt += holsu[i];

	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int N, cnt = 0;
	cin >> N;

	while (N--) {
		int n;
		cin >> n;

		if (n % 2 == 0) cnt += n;
		else holsu.push_back(n);
	}
    
    // 정렬
	sort(holsu.begin(), holsu.end());
    
    // 출력
	cout << cnt + holsuSum() << '\n';

	return 0;
}

 사탕을 최대한 많이 가져가야 하므로 사탕이 짝수로 들어있는 묶음은 모두 구매해야 한다. 그리고 홀수로 들어있는 묶음은 총 개수와 같거나 작은 가장 큰 짝수만큼 큰 묶음부터 구매하면 된다.