[SWEA] 10204 초밥 식사

출처: SWEA

Approach

Greedy 문제로

A와 B가 본인의 행복도를 높이면서 상대방의 행복도를 낮추어야 한다. 🤷‍♀️

모든 경우의 수 탐색하면 TLE 발생

 

문제 해결한 방법은 초밥(접시)에 {A의 행복도} + {B의 행복도}의 합을 기준으로 정렬한다.

(자신의 행복도를 최대화 하며서, 상대방 행복도를 최소화 하기위한 전략)

 

그리고 A와 B가 번갈아가며 먹었을 때, 행복도를 계산하는 것이다.

(N이 짝수가 아닐 수 있으므로 A가 B보다 한번 더 먹고 끝날 수 있다.)

---

#include <stdio.h>
#define LL long long

const int MAX_N = 1e5 + 5;
struct Info {
    int ah, bh;
    LL sum;
}food[MAX_N], tmp[MAX_N];

inline void swap(Info& A, Info& B)
{
    Info tmp = A;
    A = B;
    B = tmp;
}
int TC, N;
LL aHappy, bHappy;

void input()
{
    // 접시 수
    scanf("%d", &N);
    // i번 접시를 먹었을 때 a, b의 행복도
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &food[i].ah, &food[i].bh);
        food[i].sum = food[i].ah + food[i].bh;
    }
}

void quickSort(int left, int right) {
    int s = left, e = right;
    int pivot = food[(left + right) / 2].sum;
    while (s <= e) {
        while (food[s].sum > pivot) s++;
        while (food[e].sum < pivot) e--;
        if (s <= e) {
            if (s != e) {
                swap(food[s], food[e]);
            }
            s++; e--;
        }
    }
    if (left < e)
        quickSort(left, e);
    if (s < right)
        quickSort(s, right);
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc)
    {
        // init
        aHappy = bHappy = 0;
        input();
        // {a + b} 기준으로 정렬
        quickSort(0, N - 1);
        // a -> b 순으로 번갈아가면 초밥 먹기
        for (int i = 0; i < N; i++) {
            aHappy += food[i++].ah;
            if (i < N) {
                bHappy += food[i].bh;
            }
        }
        printf("#%d %lld\n", tc, aHappy - bHappy);
    }
    return 0;
}