BOOKSTORE 질문입니다

  • logickaiser
    logickaiser

    방식이 맞는 거 같은데 오답이 뜨네요.

    문제 링크

    1. M개의 벡터에 pair<책가격, 포인트> 대입
    2. 각각의 벡터 포인트에 대한 오름차순으로 정렬
    3. M개의 벡터 각각에 대해 최소 가격 계산 3.1 포인트가 큰 데이터부터 pop 3.2 pop된 데이터에 대해 쌓인 포인트가 있으면 소진하고, 남은 가격 지불 3.3 pop된 데이터의 포인트 쌓기
    4. 각각 계산된 최소 가격 중 최소 가격 출력

    방식이 잘못된 것인지, 어떤 케이스에 오동작하는 것인지 조언 부탁 드립니다.

    using namespace std;
    
    #define REP(i,n) for(int i=0; i<n; ++i)
    
    int N, M;
    
    bool MyDataSortPredicate(const pair<int, int> l, const pair<int, int> r){
        return l.second < r.second;
    }
    
    int main(void)
    {
        int t;
        cin >> t;
        while (t--)
        {
            cin >> N >> M;
    
            vector<vector<pair<int, int> > > data(M);
    
            REP(i, N){
                REP(j, M){
                    int d1, d2;
                    cin >> d1 >> d2;
    
                    data[j].push_back(make_pair(d1, d2));
                }
                REP(j, M)
                    sort(data[j].begin(), data[j].end(), MyDataSortPredicate);
            }
    
            int tmp = 0;
            int minVal = 10000 * 200;
            int pointRemained = 0;
            REP(i, M){
                while (data[i].size()){
                    int d1 = data[i].back().first;
                    int d2 = data[i].back().second;
                    data[i].pop_back();
    
                    if (d1 >= pointRemained) {
                        d1 -= pointRemained;
                        pointRemained = 0;
                    }
                    else {
                        d1 = 0;
                        pointRemained -= d1;
                    }
                    tmp += d1;
                    pointRemained += d2;            
                }
                minVal = min(minVal, tmp);
                tmp = 0;
                pointRemained = 0;
            }
            cout << minVal << endl;
        }
    }
    

    6년 전
2개의 댓글이 있습니다.
  • Being
    Being

    코드에 두 줄 순서가 바뀌어야 할 곳이 있는 것 같네요.


    6년 전 link
  • logickaiser
    logickaiser

    그러네요.... else안에 두줄이 서로 바뀌었군요!!! 감사합니다 ㅋ


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.