BOJ 28359 수열의 가치

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/28359

🧐 관찰 및 접근
#

일단 모두 $P$에 몰아넣거나, $Q$에 몰아넣거나는 가능하니 일단 기본적으로 모든 원소의 합정도는 여유롭게 가능하다.
그런데, 모든 수가 같다고 생각해보자. 그러면 모든 수는 $P$와 $Q$에 동시에 속하는데…
- 동시에 속할 수 있는 수를 어떻게 제어할 수 있지?
동시에 속한 수가 서로 다른 여러개의 수일 수는 없다.
- 어떤 수와 그 개수를 곱한 값이 최대인 수를 골라서, 맨 뒤로 보내자.

💻 풀이
#

코드 (C++):

void solve(){
    int N; cin >> N;
    map<int, int> mp;
    int ans = 0;
    rep(i, 0, N){
        int x; cin >> x;
        mp[x]++;
        ans += x;
    }
    int mxIdx = -1, mxVal = -1;
    for(auto [k, v]: mp){
        if(k*v > mxVal){
            mxVal = k*v;
            mxIdx = k;
        }
    }
    ans += mxVal;
    vector<int> v1, v2;
    for(auto [k, v]: mp){
        if(k < mxIdx) rep(i, 0, v) v1.push_back(k);
        else if(k > mxIdx) rep(i, 0, v) v2.push_back(k);
    }
    rrep(i, 0, v2.size()) v1.push_back(v2[i]);
    rep(i, 0, mp[mxIdx]) v1.push_back(mxIdx);
    cout << ans << '\n';
    for(auto x: v1) cout << x << ' ';
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#