BOJ 1715 - 카드 정렬하기

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

1715번: 카드 정렬하기

본 문제의 요점은 '현재 상태에서 값이 작은 두 묶음을 합치는 것이 최적해이다.' 입니다.

 

$A$를 최솟값이 앞으로 오도록 정렬한 배열이라고 합시다.

처음에는 정답이 $A_2 + \sum_{i=1}^{N} (A_i\times (N-i+1))$ 라고 생각했으나, 두 값을 합치는 과정에서(이때의 최소값들을 $Min_1$, $Min_2$라고 합시다.) 이 두 값보다 커지는 케이스가 발생합니다. 따라서, PQ(우선순위 큐)를 통해 각 상태에서 최솟값들을 갱신해야 할 필요가 있습니다.

 

풀이1(실패)

int arr[100005];

int main() {
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N, less<>());
    int tmp = N-1;
    ll ans = 0;
    ans += arr[0]*(N-1);
    for(int i=1; i<N; i++) {
        ans += arr[i]*tmp;
        tmp--;
    }
    cout << ans;
}

 

풀이2(AC, PQ사용)

priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        int X;
        cin >> X;
        pq.push(X);
    }
    ll ans = 0;
    while(pq.size()!=1) {
        int First = pq.top(); pq.pop();
        int Second = pq.top(); pq.pop();
        ans += First + Second;
        pq.push(First+Second);
    }
    cout << ans;
}