[algospot] SUSHI

문제링크 입니다

메모이제이션 동적 계획법을 이용하여 풀면 MAX_BUDGET을 10 억으로 정의하여 10억 개짜리 배열을 잡아야합니다.

• 해결하기 위해 메모리 사용량을 줄일 수 있는 반복적 동적 계획법을 이용한다.
• 또한 초밥의 가격은 최대 2만원이므로 슬라이딩 윈도우를 사용하여 cache[budget-20000] 전의 원소들은 신경 쓰지않고 배열을 잡는다.
• 그리고 초밥의 가격은 100의 배수 이므로 모든 가격을 100으로 나누어준다.

[SUSHI] 문제 😒😒😒😒😒

문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.

운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합시다. 이 때 얻을 수 있는 최대한의 선호도는 얼마일까요?

입력

입력의 첫 줄에는 테스트 케이스의 수 c(1 <= c <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 초밥의 종류 n(1 <= n <= 20)과 운영진들의 예산 m (1 <= m <= 2,147,483,647)이 주어집니다. 그 후 n 줄에 각 초밥의 가격과 선호도가 순서대로 주어집니다. 가격은 20,000 이하의 자연수로, 항상 100 의 배수입니다. 선호도는 20 이하의 자연수입니다.

출력

각 테스트 케이스별로 한 줄에 가능한 선호도의 최대 합을 출력합니다.

입력 예제

2
6 10000
2500 7
3000 9
4000 10
5000 12
10000 20
15000 1
6 543975612
2500 7
3000 9
4000 10
5000 12
10000 20
15000 1

출력 예제

28
1631925

전체 코드는 다음과 같습니다.

//
//  SUSHI.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/15.
//

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

ifstream fin("SUSHI.txt");
int N; // 초밥의 종류
int M; // 운영진들의 예산
int cache[201]; // 최대 20000원의 가격을 100으로 나누면 200 가지 +1
vector<pair<int,int>> menu; // first -> 가격 second -> 선호도
int SUSHI(){
    int ret = 0;
    cache[0] = 0;
    for(int budget=1;  budget <=M; budget++){
        int cand = 0;
        for(int dish =0; dish<N; dish++){
            if(budget >= menu[dish].first){
                cand = max(cand, cache[(budget-menu[dish].first)%201] + menu[dish].second);
            }
        }
        cache[budget%201] = cand;
        ret = max(ret, cand);
    }
    return ret;
}
/*
 메모이제이션 동적 계획법 알고리즘
int cache[MAX_BUDGET+1];
int SUSHI(int budget){
    // 기저사례
    if(budget < 0) return 0;
    int &ret = cache[budget];
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=0; i<N; i++){
        if(budget < menu[i].first) continue;
        ret = max(ret, SUSHI(budget-menu[i].first) + menu[i].second);
    }
    return ret;
}
*/
int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;

    for(int i = 0; i < test_case; i++){
        fin >> N >> M;
        M = M/100;
        memset(cache, -1, sizeof(cache));
        int price;
        int preference;
        menu.clear();
        for(int j=0; j<N; j++){
            fin >> price >> preference;
            price /= 100;
            menu.push_back(make_pair(price,preference));
        }
        cout << SUSHI() << endl;

    }
    return 0;
}