백준 1202번: 보석 도둑 풀이

해결 방법
1. 가방과 보석을 무게순으로 오름차순으로 정렬한다.
- qsort 사용해서 쉽게 정렬함!

2. 무게가 작은 가방부터 보석들의 무게와 비교하며 들어갈 수 있는 보석이라면 temparr(힙)에 넣기!

temparr은 보석의 가격 순으로 정렬해야함 => 가방무게와 보석무게를 계속 비교하고 들어갈 수 있다면 계속 들어와야하니까

push

3. pop 하면서 getmoney(도둑이 가지는 돈)에 더해주기

 
전체 코드

#include<stdio.h>
#include<stdlib.h>

typedef struct Info {
    int money;
    int weight;
    int check;
} Info;

int top, bagtop, temptop;
Info arr[390001], bag[390001], temparr[390001];

int push(int money) {
    temparr[++top].money = money;
    
    for(int i=top; i>1; i=i/2)
    {
        if(temparr[i/2].money<temparr[i].money) {
            Info temp = temparr[i/2];
            temparr[i/2] = temparr[i];
            temparr[i] = temp;
        }
    }
    
    return 0;
}

void pop(void) {
    temparr[1] = temparr[top--];
    if(top<0) top=0;
    
    for(int i=1; i*2<=top;)
    {
        if((i*2+1)<=top)
        {
            if(temparr[i*2].money>temparr[i*2+1].money)
            {
                if(temparr[i*2].money>temparr[i].money)
                {
                    Info temp = temparr[i*2];
                    temparr[i*2] = temparr[i];
                    temparr[i] = temp;
                    
                    i=i*2;
                }
                else break;
            }
            else
            {
                if(temparr[i*2+1].money>temparr[i].money)
                {
                    Info temp = temparr[i*2+1];
                    temparr[i*2+1] = temparr[i];
                    temparr[i] = temp;
                    
                    i=i*2+1;
                }
                else break;
            }
        }
        else
        {
            if(temparr[i*2].money>temparr[i].money)
            {
                Info temp = temparr[i*2];
                temparr[i*2] = temparr[i];
                temparr[i] = temp;
                
                i=i*2;
            }
            else break;
        }
    }
}

int compare(const void *a, const void *b) {
    return ((Info*)a)->weight > ((Info *)b)->weight;
}

int main(void) {
    int n, k;
    long long int getmoney=0;
    
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++) {
        scanf("%d %d", &arr[i].weight, &arr[i].money);
    }
    
    qsort(arr, n, sizeof(Info), compare);
    
    for(int i=0; i<k; i++) {
        scanf("%d", &bag[i].weight);
    }
    
    qsort(bag, k, sizeof(Info), compare);
    
    int j=0;
    for(int i=0; i<k; i++) {
        
        while(j<n) {
            if(arr[j].weight <= bag[i].weight) {
                push(arr[j].money);
                j++;
            }
            else break;
        }
        
        if(top!=0) {
            getmoney += temparr[1].money;
            pop();
        }
    }
     
    printf("%lld", getmoney);
    return 0;
}