[BOJ] 16287 Parcel

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제를 풀기 위해서는 주어진 배열에서 서로 다른 원소 2개를 뽑아 더한 값을 구한 뒤, 이를 목표값 w에서 뺀 값을 또다른 두 개의 원소의 합으로 만들 수 있는지를 확인해야 한다. 처음에는 이를 확인하기 위해 서로 다른 원소 2개를 뽑아 더한 값을 전부 저장한 sum 배열을 만들어 이를 정렬한 뒤 이분 탐색을 통해 구하는 방법을 생각했지만, sum 배열의 최대 길이가 5,000*5,000 = 25,000,000이므로 정렬이 불가능했다. 따라서 정렬을 사용하지 않는 다른 방법이 필요했고, 다음과 같은 방법을 사용하기로 했다.

 

1. 서로 다른 두 개의 원소 합을 저장하는 배열 weight를 만든다.

2. 이중 for문을 돌리며 서로 다른 두 개의 원소 합을 구하고, 이를 목표값 w에서 뺀 값을 i라 했을 때 weight[i]의 값이 1인지 확인한다. 1일 경우 YES를 출력하고 종료.

 

3. 안쪽 루프가 끝날 때마다 weight 배열의 값을 갱신한다.

 

전체 코드는 아래와 같다.

#include <iostream>
using namespace std;

const int MAX = 5000;
int arr[MAX], weight[800001];
int main() {
	int i, j, n, m, sumSz=0; // arr : 입력 배열, sum : arr에서 원소 두 개를 뽑아 구한 합을 저장
													 // sumSz : sum 배열 크기
	cin >> m >> n;
	for (i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			int sum = arr[i] + arr[j];
			if (sum > m) continue; // 두 원소 합이 목표값보다 크다면 pass
			if (weight[m - sum]) {
				cout << "YES";
				return 0;
			}
		}
		for (j = 0; j < i; j++) { //j를 i 이전까지 돌려서 중복 원소가 나오는 것을 방지한다.
			if (arr[i] + arr[j] < m) weight[arr[i] + arr[j]] = 1;
		}
	}
	cout << "NO";
}