[BOJ] Parcel - Compy's Blog

Parcel

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	(10 ≤ w ≤ 799,994 4 ≤ n ≤ 5,000)	Dynamic Programming, PreSum

일단 이거는 Meet in the middle 요거 사용한다고 하는데 그렇게 직관적인 사용은 아니고.. 이 네개의 값을 어떻게 시간 안에 우겨넣지? 라는 생각으로 풀다보면 solution이 나오게 되긴 합니다.

처음에는 두개씩 묶어서 이분 탐색으로 찾으려고 했는데 문제가 제가 생각한 느낌이 아니라서 좌절되고, 이후에 조금 생각해보니 아 이거 각 조합에다가 그냥 이중 두번 사용하면 좋겠다 이렇게 됐는데…

사실 이것도 시간초과가 납니다. 이게 그냥 이중이 아니라 안에 한번더 포문이 돌아가는데 별로 크지 않다고 생각했던게 아니였던 것이였죠.. 허ㅓㅎㅎ

그래서 생각했던게.. “최대인 놈 하나만” 찾으면 된다는 것에서 어차피 순차적으로 1부터 n까지 돌때 더했던 값을 맨 마지막으로 업데이트 시켜놓고 포문을 다시 1부터 n까지 돌게 시키면 제일 빨리 나올 수 있게 되면서 중복도 피할 수 있게 만들 수 있습니다. 그래서 그렇게 짰더니? 다행이 AC가 나오더군요..

다른 분들 풀이를 보니 저처럼 푼 분들이 많은 것으로 보였습니다. 하튼 생각보다 재미있는 문제였습니다.

정답 코드

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int w, n;
int nums[5001];
pair<int,int> dp[400'001];



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> w >> n;
    
    for(int i = 1; i <= n; i++) cin >> nums[i];
    
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++) dp[nums[i]+nums[j]] = {i, j};
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            int current = w - nums[i] - nums[j];
            if(!(1 < current && current < 400'001)) continue;
            if(dp[current].first == i || dp[current].second == j || dp[current].first + dp[current].second == 0
               || dp[current].first == j || dp[current].second == i) continue;
            
//            cout << i << " " << j << " " << dp[current].first << " " << dp[current].second << "\n";
            cout << "YES";
            return 0;
            
        }
    }
    
    cout << "NO";
    
    
    return 0;
}
/*
 10 6
 2 3 3 4 5 1
 */