스시문제좀 도와주세요

  • windsiren
    windsiren

    #include
    #include

    using namespace std;

    int main()
    {
    int nTestCase = 0;
    cin >> nTestCase;
    while (nTestCase--)
    {
    int nRows = 0;
    cin >> nRows;

    long long nPrice = 0;
        cin >> nPrice;
    
        map< long long, long long > map_ItemTable;
        while (nRows--)
        {
            long long nItemPrice = 0;
            cin >> nItemPrice;
    
            long long nPriority = 0;
            cin >> nPriority;
    
            map_ItemTable.insert( make_pair( nItemPrice, nPriority) );
        }
            long long nResult = 0;
            map< long long, long long >::iterator iter;
            for (iter = map_ItemTable.begin(); iter != map_ItemTable.end(); iter ++ )
            {
                long long nPriority = iter->second;
                long long nItemPrice = iter->first;
    
                long long nMulti = nPrice / nItemPrice;
                long long nTotalPriority = nPriority * nMulti;
                if (nTotalPriority > nResult)
                {
                    nResult = nTotalPriority;
                }
            }
    
            cout << nResult << endl;
    
    }
    
    return 0;

    }

    테스트 케이스대로는 입력해서 답이 잘 나오는데
    제출하면 계속 오답으로 나오네요.. 제가 너무 쉽게 생각한건지.

    해결방식은 총 금액에서 각각 목록의 금액을 나누고 그 중
    가장 높은 우선순위를 저장하여 출력하는 형식으로 했습니다.

    OVERFLOW가 발생했나싶어 자료형도 모두 LONG LONG 형으로 바꾸었는데도 그대로 오답이라 혹시 IN/OUT에 문제 있나 싶어 확인해봤으나 제가 볼때는 제대로 맞춘거같은데 안되네요.

    아니면 애초부터 testcase의 답은 맞았더라도 문제 자체가 제가 이해한거랑 달라서 다른 케이스에서 걸리는지..


    8년 전
2개의 댓글이 있습니다.
  • Elevista
    Elevista

    unbounded knapsack problem 문제인데 아직 자세히 공부를 안해서 풀이는 모르겠지만
    탐욕적으로는 아무래도 오답 없이 풀기는 힘들지 않을까 싶어요.
    최적값 찾는 문제에서 예제는 잘 풀리는데 돌려보면 틀리는 경우가
    탐욕법으로는 안되는 문제인 경우인게 흔한 것 같아요.
    문제 분류가 동적계획법인데 동적 계획법으로 푸셔야 할듯


    8년 전 link
  • windsiren
    windsiren

    답변 감사합니다. 하루지나서 문제를 보니 제가 문제 자체를 오해했네요.
    탐욕적으로 풀지 말아야된다는것도 이해가 됐습니다.


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