[BOJ] 행운쿠키 제작소

행운쿠키 제작소

TimeLimit	MemoryLimit	Condition	TAG
5s	128MB	(1 ≤ N ≤ 1,000)	Dynamic Programming

요즘 푸는 문제들이 전부 dp여서 좀 이제 다른거 풀긴 해야되는데… 랜디 중이여서 어쩔 수 없나봅니다.

사실 몇 번 거르긴 했는데 수학은 저한테 너무 어려워요. 이상한 정수론 나오면 자력을 풀기가 너무 빡세서 넘기고 이러고 있어서..

뭐 중간에 crypto 배운 짬바 어디갔나 싶지만.. ㄹㅇ 자력으로는 좀 힘들더라구요.

하튼 이번 문제는 아이디어가 쉬운 편이었는데.. 생각해내는게 꽤 오래걸렸습니ㅏㄷ.

포인트는 결국 순서는 아니고 그냥 점수에 포커스를 맞춰서 생각하면 금방 풀 수 있는 정도 인 것 같습니다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = unsigned long long;
using ld = long double;
//ll MOD = 1'000'000'007;
//ll MOD = 1.8446744074E19;
int T;


ll dp[1001 * 101];
// 와 잠만 개크랙 생각남
// 그니까 사실 순서가 중요한게 아님 사실
// 그냥 점수가 중요한건데.. 지금보면
// 둘 중 하나를 선택하는 거자나..
// 이게 포인트야
// 하나를 다 먹었다고 가정을 해. 그담에 어떤걸 교체할건지를 정할거야.
// 근데 여기서 하나 더 나가자면.. 내가 가지고 있는 포인트도 알고, 바꿀 포인트를 알면 되는건데. 이때 한쪽 포인트가 I일 때 다른 오븐 포인트 j가 최소인 경우를 구해서
// 그거의 맥스를 찍으면 되는거구나 이렇게 하는게 아닐까?
//근데 구현을 이제 dp로 가능할거 같으넫

// dp 자체를 저 i에 대한걸로 하면 될듯?

ll solution(){
    int N;
    cin >> N;
    
    pair<int, int> lucks[1001];
    
    ll start = 0;
    for(int i = 0; i < N; i++){
        cin >> lucks[i].first >> lucks[i].second;
        start += lucks[i].first;
    }
    for(int i = 0; i < 101 * N; i++)
        dp[i] = LLONG_MAX;
    
    
    dp[start] = 0;
    
    
    for(int i = 0; i < N; i++){
        // 시간복잡도가 이게 맞는지 모르겠네..
        
        for(int j = 0; j < N * 101; j++){
            if(dp[j] == LLONG_MAX) continue;
            dp[j - lucks[i].first] = min(dp[j - lucks[i].first], dp[j] + lucks[i].second);
        }
    }
    
    ll result = LLONG_MAX;
    
    for(ll i = 0; i < 101 * N; i++)
        result = min(result, max(dp[i], i));
    
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> T;
    
    while(T --> 0){
        cout << solution() << "\n";
    }

    return 0;
}