Ratatouille

문제파악

레시피를 구성하는 재료가 package 단위로 존재하며 이를 묶어서 kit로 고객에게 제공 할 때 kit로 만들 수 있는 요리의 수와 상관없이 만들 수 있는 kit 수의 최대값을 구하는 문제입니다. kit를 구성할 때 각 재료의 무게는 kit가 만들 수 있는 수만큼의 요리를 만들 때 필요한 재료의 90 ~ 110%를 만족해야합니다.

IDEA

공식 사이트의 분석글에 보다 자세한 설명이 기술되어 있습니다.

1. 한 package가 반드시 단일 갯수의 요리만을 만들 수 있는 것이 아닙니다

   예시로 주어진 입력값의 6번째 케이스를 보면 첫 번째 재료의 1260g 패키지는 17, 18, 19, 20개의 요리를 만드는 kit에 포함 될 수 있습니다.

2. 따라서 kit를 어떤 package들을 엮는지에 따라 만들 수 있는 갯수가 달라집니다.

3. kit를 구성해나갈 때 가장 범용성이 떨어지는 package들만을 선택하여 구성합니다.

4. 각 패키지들을 재료별로 만들 수 있는 요리수의 최소값이 제일 적고 최대값이 제일 작은 순으로 정렬합니다.

5. 각 패키지별 첫번 째 요소들을 뽑아 kit를 구성시킬 수 있는 지 확인하고 불가능할 시 만들 수 있는 요리 수의 최대값이 가장 작은(범용성이 떨어지는) package를 삭제하고 다시 kit 구성을 시도합니다. kit 구성이 가능한 경우 결과값 개수를 1 증가시키며 해당 package들을 모두 삭제합니다.

공식 분석글에는 heap(priority queue)를 사용하여 해결 가능하다 서술되어있지만 intersection 관리를 하는 방법이 떠오르지 않아 코드 구성시 단순히 최소값을 유지하며 kit 구성 불가능시 이를 삭제하고 다시 처음 부터 kit 구성을 시도하도록 만들었습니다.

CODE

/*
* unit : 요리 하나를 만들기 위해 필요한 각 재료별 무게
* package : 재료 별 package들의 무게
*/
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int N, P;
vector<pair<int,int>> packages[50];
vector<int> unit;

bool compare_packages(pair<int, int> lp, pair<int, int> rp){
    if(lp.first == rp.first){
        return lp.second > rp.second;
    }
    else{
        return lp.first > rp.first;
    }
}

int main(){
    int T, temp, l, r, m, result;
    scanf("%d", &T);
    for(int t= 1; t<T+1; t++){
        result = 0;
        for(int i= 0; i<50; i++){
            packages[i].clear();
        }
        unit.clear();

        scanf("%d %d", &N ,&P);
        for(int n=0; n<N; n++){
            scanf("%d", &temp);
            unit.push_back(temp);
        }
        for(int n=0; n<N; n++){
            for(int p=0; p<P; p++){
                scanf("%d", &temp);
                /// 만들 수 있는 요리 수의 범위를 구함(l : 최소, r : 최대)
                l = (10*temp);
                if(l%(11*unit[n])){
                    l = l/(11*unit[n]) + 1;
                }
                else{
                    l = l/(11*unit[n]);
                }
                r = (10*temp)/(9*unit[n]);

                if(l > r)
                    continue;

                packages[n].push_back({l,r});
            }
            /// package들을 재료별로 만들 수 있는 요리 수의 최소값이 제일 작고 최대 값이 제일 작은 순으로 정렬
            sort(packages[n].begin(), packages[n].end(), compare_packages);
        }
        while(1){
            /// min_pair의 재료 index
            m = 0;
            if(packages[0].empty()){
                break;
            }
            /// 만들 수 있는 요리 수의 최대값이 제일 작은 범위
            pair<int, int> min_pair = packages[0].back();
            /// 현재까지 package들로 만들 수 있는 요리수의 범위
            pair<int, int> intersection = min_pair;

            for(int n=1; n<N; n++){
                if(packages[n].empty()){
                    /// package가 더이상 존재하지 않아 요리 만들기 불가
                    m = -2;
                    break;
                }
                pair<int, int> t_pair = packages[n].back();
                if(t_pair.second < min_pair.second){
                    m = n;
                    min_pair = t_pair;
                }
                if(intersection.first > t_pair.second || intersection.second < t_pair.first){
                    /// intersection이 없어져 요리 만들기 불가. min_pair를 해당 재료에서 삭제
                    packages[m].pop_back();
                    m = -1;
                    break;
                }
                if(intersection.first < t_pair.first)
                    intersection.first = t_pair.first;
                if(intersection.second > t_pair.second)
                    intersection.second = t_pair.second;
            }
            if(m== -2){
                break;
            }
            else if(m != -1){
                /// kit 구성 성공 해당 package들 삭제
                result += 1;
                for(int n=0; n<N; n++){
                    packages[n].pop_back();
                }
            }
        }

        printf("Case #%d: %d\n", t, result);
    }
}