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) );
}
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의 답은 맞았더라도 문제 자체가 제가 이해한거랑 달라서 다른 케이스에서 걸리는지..
9년 전