[백준]16287 Parcel

[정답이 아니라 풀이 기록입니다.]

Parcel

여러개의 수가 주어진다. 그 중 4개를 골라 더했을 때 W가 나올 수 있는지 구하시오.

접근

1. 5000개중 4개를 직접 뽑는 것은 너무 시간이 오래걸립니다. (O(5000^4))
2. 2개를 뽑는 것은 주어진 시간 내에 할 수 있습니다. (O(5000^2)

구현

중간에서 만나기

4개를 선택하는 것은 위에서 이야기했듯 시간초과가 납니다.
이 문제에서는 4개의 수의 위치, 순서에 상관없이 단순히 더해서 W가 되는지가 중요합니다.
수를 4개 선택했다 가정해봅시다.

{A, B, C, D}

---

A+B+C+D

4개를 선택해서 더했습니다.
그런데 생각해보면 2개 그리고 2개를 따로 선택해서 더해도 값은 같게 나옵니다.

{A, B} {C, D}

---

A+B+C+D

이렇게 시간복잡도가 제곱 단위로 걸리는 경우 n이 커지면 소모시간이 매우 커지기에 가능하다면 나눠서 계산하고 중간에서 만나서 합치는 것이 이득입니다.

이것이 mitm(meet in the middle) 중간에서 만나기입니다.

기준 점

나눠서 구할 때 기준 점이 중요합니다.
기준점이 고정된 상태라면 기준점 왼편에서 4개를 선택하는 경우 중 답이있는 상태가 될 수 있습니다.
그렇기에 기준점인 i를 3에서 부터 n-1 까지 변경시켜가며 확인합니다
i 왼편에서 2개를 선택하고, i를 포함하는 오른편에서 2개를 선택한다면 모든 경우를 확인 할 수 있는거죠!

for (int i = 2; i < n-1; i++) { //벡터라 인덱스가 1씩 빠집니다.

그리고 오른쪽에서 원소를 뽑고 바로 합이 W가 될 수 있는지 확인 할 수 있게 임의의 수가 있는지 바로 확인 할 수 있는 테이블을 만들어 왼편에서 뽑은 수들의 합을 저장할 수 있게 해둡니다.

bool table[800000]; //ex) a = 10 , b= 6 이라면 a+b = 16, table[16] = true

왼편에서 2개 구하기

먼저 왼편에서 2개를 구해봅시다. 이때 중복된 경우는 계산할 필요가 없습니다.

i-1을 기준점으로 했을때 계산을 다 끝내고 i가 기준점이라 가정해봅시다.
i-1은 계산을 다 끝냈기에 1 ~ i-2번 원소들 중에서 2개를 뽑은 경우는 이전에서 i-1에서 계산되었을 것입니다.

그렇기에 기준점이 i인 곳에서는 i-1번 원소를 뽑고, 1~ i-2번 원소에서 한개를 뽑는 경우를 구합니다.

(i, i-1, i-2 로 따라올라가다보면 기준점이 3인 곳이 나옵니다. 기준점이 2일 수 없고 (1~1에서 두개를 뽑을 수 없음), 3에서는 성립하기에 전체가 성립합니다.)

이 뽑은 원소의 합은 위에서 만들어둔 테이블에 저장합니다.

for (int i = 2; i < n-1; i++) {
		for (int j = 0; j < i - 1; j++) {
			table[v[j]+v[i-1]] = true;
        }
}

오른편에서 2개 구하기

다음으로 오른편에서 2개를 구해봅시다.
위와 비슷하게 생각해서 기준점이 i일때 기준점은 증가하기에 i+1 ~ n까지중 2개를 뽑는 경우는 기준점이 i+1일때 계산될 것입니다.
그렇기에 기준점이 i일때는 i번 원소를 뽑고 i+1~n번 원소 중에서 1개를 뽑으면 됩니다.

for (int i = 2; i < n-1; i++) {
		for (int j = 0; j < i - 1; j++) {
			table[v[j]+v[i-1]] = true;
		}

		for (int j = i + 1; j < n; j++) {//i+`~n번 원소 중 1개 선택
		
		}
}

답 구하기

오른편에서 2개를 구했다면 답을 계산할 수 있습니다.
왼편에서 뽑은 원소를 a,b 오른편에서 뽑은 원소를 c,d라 하였을때, a+b+c+d의 합이 W여야하기에
table[W-(c+d)]가 true인지 확인하면 됩니다.

이때 c+d가 W보다 크면 음수번 인덱스에 접근할 수 있기에 탈출하도록 처리해둡니다. 그리고 답을 찾으면 for문을 더 돌 필요가 없기에 탈출합니다.

bool answer = false;

for (int i = 2; i < n-1; i++) {
		for (int j = 0; j < i - 1; j++) {
			table[v[j]+v[i-1]] = true;
		}

		for (int j = i + 1; j < n; j++) {
			if (v[j] + v[i] >= w) {
				break;
			}

			if (s[w - (v[j] + v[i])] == 1) {
				answer = true;
				break;
			}
		}
        if(answer){
        	break;
        }
}

그리고 답을 출력합니다.

if(answer){
	printf("YES");
}else{
	printf("NO");
}

마무리

2 * n^2이니까 대략 O(n^2)정도 이겠네요.
mitm은 어렵지 않으나, 원소의 중복 선택을 처리하는 것이 어려운 문제였습니다.

끝