BOJ 28062 - 준석이의 사탕 사기 링크
(2023.05.25 기준 B2)

문제

사탕이 ai개 들어있는 사탕 묶음이 N개가 있다. 마음껏 살 수 있으나 총 사탕의 개수가 짝수가 되게끔 산다고 했을 때, 최대로 살 수 있는 총 사탕의 개수 출력

알고리즘

그리디와 홀수와 짝수의 성질

풀이

홀수 + 홀수 = 짝수. 이는 누구나 아는 사실이다. 짝수 + 짝수 = 짝수. 이도 자명하다.
위 두 성질을 이용하여, 일단 모든 짝수 개의 사탕 묶음은 모두 살 수 있다. 문제는 홀수 개의 사탕 묶음들.

홀수는 수의 크기와 상관 없이 홀수 2개를 더하면 짝수가 된다. 만약, 1, 99, 101 개의 사탕 묶음이 있다면? 당연히 99개와 101개를 사야 한다.
그러므로 사탕 묶음을 크기 순으로 정렬하여 내림차순으로 쭉 훑으면서 홀수 개의 사탕 묶음이 두 개를 볼 때마다 그 두 개를 합쳐서 결과에 저장하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;
    int a[N]; for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a + N);

    // 홀수 + 홀수 = 짝수
    int result = 0, odd = 0;
    for (int i = N - 1; i >= 0; i--){ // 사탕 묶음의 개수가 큰 것부터 시작
        if (a[i] & 1){ // 홀수면 따로 빼두자.
            if (odd) // 만약 따로 빼둔 홀수가 이미 있으면 홀수끼리 더해서 결과에 더하자.
                result += odd + a[i], odd = 0;
            else odd = a[i];
        }
        else // 짝수면 바로 결과에 더하자.
            result += a[i];
    }

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
a = sorted(map(int, input().split()))

# 홀수 + 홀수 = 짝수
result = odd = 0
for i in range(N - 1, -1, -1): # 사탕 묶음의 개수가 큰 것부터 시작
    if a[i] & 1: # 홀수면 따로 빼두자.
        if odd: # 만약 따로 빼둔 홀수가 이미 있으면 홀수끼리 더해서 결과에 더하자.
            result += odd + a[i]
            odd = 0
        else:
            odd = a[i]
    else: # 짝수면 바로 결과에 더하자.
        result += a[i]

print(result)