백준 Parcel(16287)

Parcel

1. 힌트

1) 부분집합을 고르는 것이므로 수열의 순서는 상관이 없습니다. 수열을 정렬해봅시다. 정렬된 수열에 대해서는 이분 탐색이나 두 포인터같은 알고리즘을 적용할 수 있습니다.

2) $N$이 $O(N^2)$까지는 가능한 범위이므로 두 원소 $a, b$를 고르는 $O(N^2)$의 전처리를 해줍니다. $R[x] =$ 두 원소를 골라 합이 $x$일 때 두 원소 중 큰 인덱스의 위치를 저장하는 것으로 정의합시다.

3) 두 원소의 합 $x$의 범위는 $3 \le x \le 399999$입니다. 모든 $x$에 대해서 $R[x]$값이 존재한다면 인덱스 $[R[x] + 1, N)$ 범위에 대해서 합이 $W- x$가 되는 경우가 있는지 확인하면 됩니다. 수열을 정렬했기 때문에 이 연산은 두 포인터로 $O(N)$에 가능합니다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

두 용액

임의의 두 수의 합을 확인하는 문제가 있었습니다. 수열을 정렬하고 이분 탐색을 적용하거나 두 포인터를 사용하면 해결 가능합니다.

세 용액

임의의 세 수의 합을 확인하는 문제도 있었습니다.
가능한 $a,\ b$ 순서쌍에 대해서 $O(N^2)$으로 모두 시도한 하면서 마찬가지로 이분 탐색으로 $O(lgN)$으로 찾는 문제입니다. $O(N)$으로 한 용액을 선택하고 두 포인터로 나머지 두 용액을 찾을 수도 있습니다.

합이 0인 네 정수

임의의 네 수의 합을 확인하는 문제도 있었습니다. 지금 보는 이 문제와 꽤 비슷해 보입니다. 서로 다른 네 수를 두 수로 만들기 위해서 $A$와 $B$에서 고를 수 있는 모든 경우의 수를 합치고, $C$와 $D$도 마찬가지로 해 주는 식으로 배열을 두 개 만들면 각각의 배열에서 한 개씩 선택하는 것으로 만들 수 있습니다.

하지만 Parcel에서는 이런식의 풀이가 불가능합니다. 서로 다른 $a,\ b,\ c,\ d$를 골라야 하기 때문입니다. $O(N^2)$의 전처리한 원소 중에서 서로 다르게 $2$개를 고르더라도 인덱스가 겹칠 수 있습니다.

2) 순서를 강제할 수 있을까?

우리는 부분 집합을 고를 수 있는지를 확인하는 것이 목표이기 때문에 주어진 수열을 정렬해도 상관 없습니다. 주어진 수열 $S$를 정렬하고, $S$에서 서로 다르게 $4$개를 고른 후에 작은 인덱스부터 $a,\ b,\ c,\ d$라고 하겠습니다. 우리가 찾고자 하는 조건은 $S[a] + S[b] + S[c] + S[d] = W$인 경우입니다. $2$개만 고르는 거면 두 포인터로 $O(N)$에 어떻게 할 수 있는데 $4$개를 $2$개로 줄이는 방법은 없을까요?

$S[a] + S[b] = x$라고 합시다. $a,\ b$만 확인한다면 $O(N^2)$으로 만들어낼 수 있는 합 $x$를 모두 확인할 수 있습니다. 그리고 $a,\ b,\ c,\ d$는 오름차순이므로 $[b + 1, N)$범위에서 두 포인터를 통해 $W - x$를 만족하는 $S[c] + S[d]$가 있는지 찾으면 됩니다. $O(N^2)$의 전처리를 위해서 배열 $R$을 다음과 같이 정의합시다.
$R[x] = (S[a] + S[b] = x)$를 만족하는 순서쌍 $a,\ b$중에서 $b$의 인덱스의 최솟값을 저장. 만약 만족하는 순서쌍이 없다면 INF를 저장.
이렇게 하면 전처리 후에 $R[x]$에 저장되어 있는 값을 보고 $[R[x] + 1, N)$까지 두 포인터로 $W - x$를 찾으면 됩니다. 그런데 왜 최솟값을 저장해야할까요?

$S[a] + S[b] = x$를 계산하는데 다음과 같은 상황이 둘 다 $S[a] + S[b] = x$를 만족한다고 합시다.
1번 $S = [t, t, S[a], t, t, S[b], t, t, t]$
2번 $S = [t, t, t, S[a], S[b], t, t, t, t]$
1번에서 $S[a] + S[b] = x$인 $(a,b)$를 찾았으니 이제 $[b + 1, N)$범위에서 $W - x$를 만족하는 $(c, d)$를 찾아야합니다. 그런데 1번에서 $(c, d)$를 찾을 수 있었다면 당연히 2번에서도 찾을 수 있습니다. 범위를 완전히 포함하면서 더 커졌으니까요. 오히려 1번에서 못찾았는데 2번에서 찾을 수 있는 경우가 있겠죠 따라서 $R[x]$는 계속 최솟값으로만 갱신해줘야 합니다.

3. 구현

public class Main {
	// 정렬된 배열 S[head, tail]에 합이 k인 두 원소가 존재하는지 반환
	static boolean f(int[] S, int head, int tail, int k) {
		while (head < tail) {
			int sum = S[head] + S[tail];
			if (sum < k) head++;
			else if (sum > k) tail--;
			else return true;
		}
		return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int W = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int[] S = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(S);
		// R[x] = S[i] + S[j] = x인 경우가 존재하는지
		// 존재한다면 (i < j) 인 j인덱스를 저장, 중복된다면 가장 작은 값. 없다면 INF
		int[] R = new int[400001];
		Arrays.fill(R, N);
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				int sum = S[i] + S[j];
				R[sum] = Math.min(R[sum], j);
			}
		}
		boolean flag = false;
		for (int x = 1; x <= 400000; x++) {
			if (f(S, R[x] + 1, N - 1, W - x)) {
				flag = true;
				break;
			}
		}
		System.out.println(flag ? "YES" : "NO");
	}

}

1) 시간 복잡도

정렬에서 $O(NlgN)$, 전처리에서 $O(N^2)$이고, 그 후에는 $O(4\times 10^5 \times N)$인데 실제로는 이보다 훨씬 빠르게 끝납니다