September 16, 2021

문제

동빈이는 두 개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.

동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.

동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 합니다.

N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하세요.

제한시간

2초

메모리 제한

128MB

입력 조건

첫 번째 줄에 N, K가 공백을 기준으로 구분되어 입력됩니다.(1≤N≤100,000, 0≤K≤N)

두 번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수입니다.

세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수입니다.

출력 조건

최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력합니다.

풀이

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N, K, sum;
vector<int> A, B;

int main() {
    int tmp;

    scanf("%d %d", &N, &K);

    for (int i = 0; i < N; ++i) {
        scanf("%d", &tmp);

        A.push_back(tmp);
    }

    for (int i = 0; i < N; ++i) {
        scanf("%d", &tmp);

        B.push_back(tmp);
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for (int i = 0; i < K; ++i) {
        if (B[N - 1 - i] > A[i]) {
            swap(B[N - 1 - i], A[i]);
        } else {
            break;
        }
    }

    for (int i = 0; i < N; i++) {
        sum += A[i];
    }
    
    printf("%d", sum);

    return 0;
}