[알고스팟 / 알고스팟] 인터넷서점 bookstore

문제

새 학기가 시작되면 항상 부담되는 것이 비싼 교과서 가격이다. 오랜 병특 생활을 마치고 복학한 스탱은 이번 학기에 사야 하는 N 권의 교과서를 인터넷 서점에서 사기로 했다. 인터넷 서점 간의 과다 경쟁으로 인해 모든 서점들은 한 권을 사더라도 무료 배송을 실시하고 있으며, 교내 서점보다 가격도 저렴하다.

그런데, 스탱은 자신이 가입해 있는 M 군데의 인터넷 서점마다 각각의 교과서 가격이 다르다는 것을 발견하게 되었다. 단순하게 한 서점이 다른 서점보다 항상 싸거나 항상 비싼 경우라면 간단하겠지만, 실제로는 교과서마다 가장 싸게 파는 서점이 서로 달랐다. 각 교과서마다 가장 싸게 파는 서점에 가서 사면 좋겠지만, 한 서점에서 책을 많이 사면 회원등급이 오르는 혜택이 있기 때문에 스탱은 서점 하나를 골라 책 전부를 구입하기로 결정했다.

문제는, 각 서점들은 포인트 제도를 실시한다는 것이다. 각 서점에서 책을 사면 책 값의 일부에 해당하는 포인트가 적립되는데, 이 포인트는 다른 책을 살 때 책값의 전부 혹은 일부를 내는 데 사용할 수 있다. 따라서, 어느 순서로 책을 구매하느냐에 따라서 결과적으로 스탱이 쓰는 돈이 달라질 수 있다.

스탱은 이와 같은 상황 하에서, 어느 서점에서 책을 사야 가장 돈을 적게 쓸 수 있을지를 알고 싶어 한다. 스탱에게는 남아 있는 포인트가 하나도 없으며, 책을 모두 구입한 뒤 남는 포인트에는 신경을 쓰지 않는다고 가정하자.

예를 들어, 다음은 스탱이 구입해야 할 교과서들의 목록과 3군데의 인터넷 서점에서의 가격 및 적립 포인트의 한 예를 보여준다.

교과서	서점 
	No24		뵤고문고		40인의 도적
	가격	포인트	가격	포인트	가격	포인트
알고스팟 저지 7일만에 만들기	5,000	500	6,000	1,200	5,500	550
동적 계획법 30분만에 마스터	3,000	300	3,000	1,000	3,500	350
10년에 마스터하는 파이썬	1,500	0	2,000	500	5,500	550
검색 엔진 for dummies	5,000	500	5,500	1,500	2,000	100

이 경우에는 전반적으로 No24 가 저렴하지만, 포인트는 뵤고문고가 훨씬 많이 적립을 해 준다는 것을 알 수 있다. 실제로 No24 에서 책을 구입하게 되면 13,200원이 들지만, 뵤고문고에서 구입하면 12,800원이면 충분하다. 어떤 서점에서 책을 구입해야 가장 적은 돈을 쓰게 되는지를 계산하는 프로그램을 작성하라.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어진다. 각 테스트 케이스의 첫 줄에는 스탱이 사야 하는 책의 수 N (1 <= N <= 200) 과 서점의 수 M (1 <= M <= 100) 이 주어지며, 그 후 N 줄에 각각 M 개의 정수 쌍이 주어진다. 이 때 i 번째 줄의 j 번째 쌍은 i 번째 책이 j 번째 서점에서 팔리는 가격과 적립 포인트를 순서대로 나타낸다.

모든 책의 가격은 10,000 이하의 자연수이며, 적립 포인트는 책의 가격보다 작은 음이 아닌 정수이다.

출력

각 테스트 케이스마다 한 줄로, 스탱이 써야 하는 최소의 금액을 출력한다.

예제 입력

1 
4 3
5000 500 6000 1200 5500 550 
3000 300 3000 1000 3500 350 
1500 0 2000 500 5500 550 
5000 500 5500 1500 2000 100 

예제 출력

12800

풀이

그리디 문제입니다. 단순하게 매번 현재 가장 이득이 되는 값을 취해주면 답을 구할 수 있습니다. 문제를 보면 포인트를 남길 필요없이 최대한 쓸 수 있는 만큼 쓰는게 좋습니다. 그래서 포인트로 정렬을 하여 큰 포인트 부터 쓰도록 하였습니다. 그리고 서점 한 곳에서 모든 책을 구매하기 때문에, 지불 할 금액을 계산할 때 포인트만 잘 써주면 쉽게 풀이할 수 있습니다. 

참고로 답안을 보시면 scanf로 입력 값을 받지 않고 fread로 한번에 모든 입력 값을 받은 이후 buff에서 숫자를 하나씩 받아오게 하고 있습니다. 이렇게 구현을 하게 되면 시간이 많이 소비되는 입출력 함수를 한번만 타면 되기때문에 이 문제와 같이 입력 값이 많은 문제에서는 한번 써볼만합니다.

그럼 잠시 고민 해 보시고 아래로 내려서 답도 확인 해보시기 바랍니다.

답안

#include <stdio.h>
#include <string.h>
#define INF 987654321

char buff[25000000];
char *p_buff = buff;

int get_num()
{
    while (*p_buff < '0' || *p_buff > '9')
        p_buff++;
    
    int ret = 0;
    do
    {
        ret = ret*10+(*p_buff - '0');
        p_buff++;
    
    } while (*p_buff >= '0' && *p_buff <= '9');
    
    return ret;
}

void q_sort(int left, int right, int (*a)[2])
{
    int pivot = a[(left+right)>>1][1], i = left, j = right;
    do
    {
        while (a[i][1] > pivot) i++;
        while (a[j][1] < pivot) j--;
        
        if (i <= j)
        {
            double temp = *(double*)&a[i][0];
            *(double*)&a[i][0] = *(double*)&a[j][0];
            *(double*)&a[j][0] = temp;
            i++;
            j--;
        }
    } while (i<=j);
    
    if (left < j)
        q_sort(left, j, a);
    if (i < right)
        q_sort(i, right, a);
}

int main()
{
    //fread(buff, 1, 1500000, freopen("infile.txt", "r", stdin));
    fread(buff, 1, 25000000, stdin);
    
    int t = get_num();
    while (t--)
    {
        int ret = INF, n = get_num(), m = get_num();
        
        int book[100][200][2] = {0,};
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                book[j][i][0] = get_num();
                book[j][i][1] = get_num();
            }
        }
        
        for (int i = 0; i < m; i++)
        {
            q_sort(0, n-1, book[i]);
            
            int cost = 0, point = 0;
            
            for (int j = 0; j < n; j++)
            {
                if (book[i][j][0] <= point)
                {
                    point += (book[i][j][1] - book[i][j][0]);
                }
                else
                {
                    cost += (book[i][j][0] - point);
                    point = book[i][j][1];
                }
            }
            if (ret > cost)
                ret = cost;
        }

        printf("%d\n", ret);
    }

    return 0;
}