[BOJ] 28464 - Potato

https://www.acmicpc.net/problem/28464

BOJ - Potato

문제 유형: 정렬, 그리디

문제 난이도: Silver V

시간 제한: 1초

메모리 제한: 1024MB

 

문제

감자튀김을 좋아하는 박 모 씨와 다르게, 성우는 감자튀김을 그렇게 좋아하지는 않는다. 어느 날 박 모 씨와 성우는 수많은 감자튀김을 받게 되었고, 이를 나누어 가지기로 했다.

책상 위에 N$N$개의 접시가 놓여있다. i$i$번째 접시에는 ai$a_i$개의 감자튀김이 있다. 박 모 씨와 성우는 다음 행동을 번갈아 시행한다.

• 책상 위에 남아있는 접시 하나를 고르고, 접시와 그 위에 놓인 모든 감자튀김을 가져간다.

이는 책상 위의 접시가 모두 사라질 때까지 반복한다. 맨 처음 접시를 가져가는 사람은 박 모 씨다.

박 모 씨는 가져가는 감자튀김의 양을 최대화하려 하고, 성우는 가져가는 감자튀김의 양을 최소화하려 한다. 두 사람이 항상 최선의 행동을 한다고 가정할 때, 성우와 박 모 씨가 최종적으로 가져가는 감자튀김의 양을 구하여라.

 

입력

첫 번째 줄에 접시의 개수 N$N$이 주어진다. (1≤N≤200 000)

두 번째 줄에 각 접시에 있는 감자튀김의 개수 a1,a2,⋯,an가 공백으로 구분되어 주어진다. (1≤ai≤10 000)

 

출력

첫 번째 줄에 성우가 가져가는 감자튀김의 양과 박 모 씨가 가져가는 감자튀김의 양을 공백으로 구분하여 출력한다.

 

풀이

입력받아서 정렬하고, 큰쪽 절반을 성우가, 작은 쪽 절반을 박모씨가 받게 한다.

그리고 홀수라면 가운데건 박모씨가 받는다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i : a) cin >> i;

    sort(a.begin(), a.end(), greater<>());
    int m = (n / 2) + n % 2;

    int A = accumulate(a.begin(), a.begin() + m, 0);
    int B = accumulate(a.begin() + m, a.end(), 0);
    cout << B << " " << A << "\n";
    return 0;
}