algospot SUSHI

문제 링크입니다: https://algospot.com/judge/problem/read/SUSHI

반복 동적계획법을 이용하여 푼 문제였습니다.

예산의 범위가 int의 양의 정수 범위와 같으므로 매우 컸기 때문에 미리 100으로 나누는 것이 핵심이였습니다.

책을 통해 슬라이딩 윈도우 기법을 처음 접했는데 상당히 유용한 것 같습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

//직관적으로 풀었을 경우 MAX_BUDGET(너무 크다)

//#define MAX_BUDGET 1000000000

const int MULTIPLIER = 100;

 

int type, cash; //스시의 종류와 갖고 있는 예산

int price[20], preference[20]; //가격과 선호도

//int cache[MAX_BUDGET + 1];

int cache[201]; //(스시의 최대 가격은 20000 그리고 100의 배수이니 100으로 나눈 200) + 1

 

//10억개 메모리를 잡는 것은 불가능

/*

//budget만큼의 예산으로 초밥을 먹어서 얻을 수 있는 최대 선호도

int sushi(int budget)

{

        //메모이제이션

        int &result = cache[budget];

        if (result != -1)

               return result;

        result = 0;

        for (int dish = 0; dish < type; dish++)

        {

               if (budget < price[dish])

                       continue;

               result = max(result, sushi(budget - price[dish]) + preference[dish]);

        }

        return result;

}

*/

 

//cash와 price[]는 이미 100으로 나누어 있다고 가정

int sushi(void)

{

        int result = 0;

        cache[0] = 0;

        for (int budget = 1; budget <= cash; budget++) //100의 배수이니 100원부터 시작

        {

               int candidate = 0;

               for (int dish = 0; dish < type; dish++)

                       if (budget >= price[dish])

                              candidate = max(candidate, cache[(budget - price[dish]) % 201] + preference[dish]);

               cache[budget % 201] = candidate;

               result = max(result, candidate);

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> type >> cash;

               if (type < 1 || type>20 || cash < 1 || cash>2147483647)

                       exit(-1);

               cash /= MULTIPLIER; //갖고 있는 예산을 100으로 나눈다

 

               for (int j = 0; j < type; j++)

               {

                       cin >> price[j] >> preference[j];

                       price[j] /= MULTIPLIER; //가격도 미리 100으로 나눈다

               }

 

               cout << sushi() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략