[백준/BOJ] 백준 16287번 : Parcel

www.acmicpc.net/problem/16287

16287번: Parcel

i는 0부터 n-1, j는 i+1부터 n-1 까지 이중 for문을 돌며 cache[A[i] + A[j]]에 j값(뒤쪽값)을 저장해 놓고,  if (cache[w - A[i] - A[j]] != -1)을 통해 w - A[i] - A[j] 값을 만들 수 있는지 확인하고, 그때 if (cache[w - A[i] - A[j]] < i)를 통해 4개의 수가 겹치지 않았는지 확인한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int w, n;
vector<int> A;
vector<int> cache(799995, -1);

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> w >> n;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;

		A.push_back(a);
	}

	string result = "NO";
	bool check = false;

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (A[i] + A[j] >= w)
				continue;

			cache[A[i] + A[j]] = j; //cache에 뒤쪽 수를 저장

			if (cache[w - A[i] - A[j]] != -1) //w - A[i] - A[j] 값을 만들 수 있을때
			{
				if (cache[w - A[i] - A[j]] < i) //4개의 수가 겹치지 않는지 확인 
				{
					result = "YES";
					check = true;
					break;
				}
			}
		}
		if (check == true)
			break;
	}

	cout << result;

	return 0;
}