제1회 보라매컵 본선 Open Contest UPSOLVING

BOJ 27277번. 장기자랑

문제 바로가기 (클릭시 이동)

시간 제한 1초 / 메모리 제한 1024 MB

즐거운 설날을 맞아 부대 장기자랑 행사가 개최된다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.

장기자랑 행사의 총관리자는 공연하는 병사들의 장기자랑 실력을 토대로 행사를 준비하던 중, 아무래도 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담감을 느껴 본 실력을 발휘하지 못할 것이라는 고민을 하게 되었다. 이에 총관리자는 각 병사의 장기자랑 실력을 순서대로 A1,A2,⋯,An이라고 할 때, 2 ≤ i ≤ N에 대하여 i번째 공연자는 실력을 max(0, Ai - A(i-1)) 만큼만 발휘할 수 있을 것이라는 가설을 세웠다. 이때, 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다. 위 가설에 따라, 총관리자는 병사들이 발휘할 수 있는 실력의 합이 최대가 되게끔 공연순서를 배치하고자 한다. 적절한 순서로 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 구하여라.

 

나의 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<int> A,B;
    int n;
    cin >> n;
    while(n--){
        int a;
        cin >> a;
        A.push_back(a);
    }
    sort(A.begin(),A.end());
    int m=A.back();
    while(A.size()!=0){
        B.push_back(A.back());
        B.push_back(A.front());
        A.pop_back();
        if (A.size()!=0){
            A.erase(A.begin());
        }
    }
    for (int i=1;i<B.size();i++){
        m+=max(0,B[i]-B[i-1]);
    }
    cout << m;
    return 0;
}

 

이 문제는 vector를 정렬 후 [An, A1, A(n-1), A2 ... ] 이렇게 배치했을때에 최댓값이 나오니까 vector A를 정렬하고 vector B에 push를 해서 m값을 더해주었다.