BOOKSTORE 문제 검토 부탁드립니다.

  • kwangswei
    kwangswei

    안녕하세요.
    BOOKSTORE 문제 풀고 있는데 어느 부분에서 잘못된 것인지 잘 모르겠어서 도움 요청 드립니다!

    제가 구현한 알고리즘은 다음과 같습니다.
    1. pair(마일리지, 가격) 으로 입력 받아서 마일리지 높은 순으로 정렬.
    2. 0번째는 놔두고 1번째 부터 연산 시작
    3. 이전 마일리지 누적 값보다 책 값이 비싸면 현재 책 값에 (책 가격 누적 값 - 마일리지 값) 을 갱신.
    4. 책 값이 더 싸면 마일리지 누적값에서 책 값만큼 뺌.

    아래 예제를 통해서 보면 루프를 돌면서 다음처럼 변합니다.
    (책 값이 각각 6000/1200, 1000/100, 500/0 일 때)
    초기 값 : 6000/1200, 1000/100, 500/0

    첫 루프 : 6000/1200, 6000/300, 500/0
    다음 루프 : 6000/1200, 6000/300, 6200/0

    제 알고리즘에 문제가 있는지,
    어떤 테스트 케이스를 돌려보면 좋을 지 조언 부탁드립니다~!!

    #include <iostream>
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    bool sort_pred(const pair<int,int>& left, const pair<int,int>& right)
    {
        return left.second > right.second;
    }
    
    int main(){
        int C;
        cin >> C;
    
        vector< pair<int,int> > data[100];
    
        while ( C-- )    {
            int N, M ;
            cin >> N >> M;
    
            for ( int i = 0; i < M; i++ )
                data[i].clear();
    
            for ( int i = 0; i < N; i++ )        {
                for ( int j = 0; j < M; j++ )            {
                    int price, point;
                    cin >> price >> point;
                    data[j].push_back( make_pair(point,price));
                }
            }
    
            for ( int i = 0; i < M; i++ )
                sort(data[i].begin(), data[i].end(), sort_pred);
    
            for ( int i =1; i < N; i++ )        {
                for ( int m = 0; m < M; m++)            {
                    if ( data[m][i].second < data[m][i-1].first )                {
                        data[m][i].first += data[m][i-1].first - data[m][i].second;
                        data[m][i].second = data[m][i-1].second;
                    }
                    else {
                        data[m][i].second += data[m][i-1].second - data[m][i-1].first;
    
                    }
                }
            }
    
            int minVal = data[0][N-1].second;
            for ( int i = 1; i < M; i++ )        {
                if ( data[i][N-1].second < minVal )
                    minVal = data[i][N-1].second;
            }
    
            cout << minVal << endl;
    
        }
    }
    

    12년 전
2개의 댓글이 있습니다.
  • kwangswei
    kwangswei

    으악 ㅋㅋㅋ 말로는 마일리지 순으로 정렬한다고 써놓고서는 코드는 가격 순으로 정렬했네요. ㅎㅎㅎㅎㅎ ㅠ.ㅠ

    해결 했습니다~!


    12년 전 link
  • JongMan
    JongMan

    이것이 rubber duck debugging의 진수로군요 ㅎㅎ


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