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의 답은 맞았더라도 문제 자체가 제가 이해한거랑 달라서 다른 케이스에서 걸리는지..
unbounded knapsack problem 문제인데 아직 자세히 공부를 안해서 풀이는 모르겠지만
탐욕적으로는 아무래도 오답 없이 풀기는 힘들지 않을까 싶어요.
최적값 찾는 문제에서 예제는 잘 풀리는데 돌려보면 틀리는 경우가
탐욕법으로는 안되는 문제인 경우인게 흔한 것 같아요.
문제 분류가 동적계획법인데 동적 계획법으로 푸셔야 할듯
windsiren
#include
using namespace std;
int main()
{
int nTestCase = 0;
cin >> nTestCase;
while (nTestCase--)
{
int nRows = 0;
cin >> nRows;
}
테스트 케이스대로는 입력해서 답이 잘 나오는데
제출하면 계속 오답으로 나오네요.. 제가 너무 쉽게 생각한건지.
해결방식은 총 금액에서 각각 목록의 금액을 나누고 그 중
가장 높은 우선순위를 저장하여 출력하는 형식으로 했습니다.
OVERFLOW가 발생했나싶어 자료형도 모두 LONG LONG 형으로 바꾸었는데도 그대로 오답이라 혹시 IN/OUT에 문제 있나 싶어 확인해봤으나 제가 볼때는 제대로 맞춘거같은데 안되네요.
아니면 애초부터 testcase의 답은 맞았더라도 문제 자체가 제가 이해한거랑 달라서 다른 케이스에서 걸리는지..
11년 전