[백준] 16225 제271회 웰노운컵

16225번: 제271회 웰노운컵

fast io 미적용

문제 확인

 

정렬과 그리디 문제입니다.

 

풀이

 

B 기준으로 정렬하고 나면 왼쪽 수와 오른쪽 수를 묶어서 왼쪽 수 들의 합을 최대화하는 문제가 됩니다.

 

B를 기준으로 정렬을 하고 나면 2 수를 묶어 왼쪽 수를 선택하게 되므로 0번째 수는 항상 선택이 되며 n-1 번째 수는 항상 고를 수 없게 됩니다.

 

 

위와 같은 경우 답은 7, 6, 5 => 18이 됩니다.

두 수를 쌍으로 묶으며 선택하는 방법을 간단하게 우선순위 큐로 구현할 수 있습니다.

초기 7을 선택 하고 2칸씩 묶어서 우선순위 큐에 삽입하면서 최댓값을 선택하고 n-2까지 탐색을 합니다.

que =[]

ans = 7

 

que = [6, 3] => 최댓값 6 선택 => [3]

answer = 13

 

que = [3, 1, 5] => 최댓값 5 선택 => [3, 1]

answer = 18

n-2 도달 후 종료하게 됩니다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
typedef struct pir {
    int a, b;
}pir;
using namespace std;
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    priority_queue <int> que;
    int n;
    pir ary[200000];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> ary[i].a;
    for (int i = 0; i < n; i++)
        cin >> ary[i].b;
    sort(ary, ary + n, [](const pir&x, const pir&y)->bool {//정렬
        return x.b < y.b;
    });
    long long ans = ary[0].a;
 
    for (int i = 1; i < n - 1; i += 2) {
        que.push(ary[i].a);
        que.push(ary[i + 1].a);//2칸 삽입
        ans += que.top();//최댓값 선택
        que.pop();
    }
    cout << ans;
}