[BOJ/백준 15903][C++] 카드 합체 놀이

문제

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

백준 15903

 

문제 내용

입력받은 원소 n개짜리 배열에 대해, 아래 과정을 m번 수행하면 된다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

m번의 과정이 모두 끝나고, 전체 원소의 합이 최소가 되도록 해야 한다.

 

문제 풀이

x와 y를 골라 두 값을 더해 카드를 덮어써야 한다.

즉, x와 y의 값은 기존과 같거나 커지게 된다. (값이 줄어드는 경우는 없다)

전체 합이 최소가 되게 하기 위해선, 매 과정마다 가장 작은 두 수를 x, y로 골라야 한다.

 

코드

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    long long sumXY = 0;
    while (m--) {
        sort(arr, arr + n);
        sumXY = arr[0] + arr[1];
        arr[0] = arr[1] = sumXY;
    }

    long long sumTotal = 0;
    for (int i = 0; i < n; i++)
        sumTotal += arr[i];
    cout << sumTotal;
}

 

문제 코드 설명

n의 범위는 2~1000, m의 범위는 0~15*n, 카드의 원소는 1~10^6까지이다.

따라서 배열과 원소의 합을 관리하는 변수의 자료형은 int가 아니라 long long으로 한다.