[BOJ] 16287 Parcel

문제: https://www.acmicpc.net/problem/16287

 

 

문제 풀이:

풀이 1:

O($N^{2}$)으로 값 2개의 합을 벡터에 저장한다. 이때, 2개의 합은 최대 400000이므로 크기만큼 미리 벡터를 선언해줄 수 있다. 2개를 합친 값이 동일한 것이 여러개 있을 수 있으므로 각 값의 위치를 저장해준다. 

2~400000(2개 합쳐서 나올 수 있는 값)들을 다 보며, 지금 값이 존재하고 (총 무게-현재 2개 합)도 존재할 때, (i,j) 서로 다른 두 쌍을 가지고 있다면 yes를 출력하고 종료한다.

 

풀이2:

풀이1처럼 풀면 굉장히 오래걸린다. 각 두 쌍에 겹치는게 있는지 확인하는 과정이 오래 걸린거였는데 이렇게 해결할 수 있다. 

이중 포문 i, j로 돌려서 2개 합을 구할 때, dp[두개 합]=j 를 저장해두고 다음에 dp[전체 합-해당 값]이 현재 i보다 값이 작으면 현재 i, j 겹치지 않는다고 판단할 수 있다. 

 

 

 

소스코드:

풀이 1:

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <functional>
#include <unordered_map>
#include <queue>
#include <string.h>
#include <cmath>  
using namespace std;


typedef pair<int, int> P;

int weight, n,arr[5001];
vector<vector<P>> v(400002);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> weight >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			v[arr[i] + arr[j]].push_back({ i, j });
		}
	}
	for (int i = 2; i < 400000; i++) {
		if (v[i].size() == 0) continue;
		int w = weight - i;
		if (w < 0||w>400000||v[w].size()==0) continue;

		for (auto k : v[i]) {
			for (auto j : v[w]) {
				if (k.first == j.first) break;
				else if (k.first == j.second) break;
				else if (k.second == j.first) break;
				else if (k.second == j.second) break;
				else {
					cout << "YES\n";
					return 0;
				}
			}
		}
	}
	
	cout << "NO\n";
	return 0;
}

 

풀이2:

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <map>
#include <vector>
#include <functional>
#include <unordered_map>
#include <queue>
#include <string.h>
#include <cmath>  
using namespace std;


typedef pair<int, int> P;

int weight, n,arr[5001],dp[400002];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> weight >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int sum = arr[i] + arr[j];
			int w = weight - sum;
			if (w < 0 || w>400000) continue;
			if (dp[w] && dp[w] < i) {
				cout << "YES\n";
				return 0;
			}
			dp[sum] = j;
		}
	}

	
	cout << "NO\n";
	return 0;
}