[BOJ] 18114 - 블랙 프라이데이

1. 문제 해석

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

18114번: 블랙 프라이데이

• N개의 물건이 있다. 물건의 무게는 모두 다르다.
• 최대 3개의 물건을 선택하여 무게 C를 맞출 수 있는 조합이 가능한 지 판단해야 하다.
• 물건의 중복 선택은 불가능하다. (1 <= N <= 5000, 1 <= C <= 10^8) 

 

2. 접근방법

선택할 수 있는 물건이 최대 3개 임으로 3중 for문을 이용하여 모든 경우를 확인할 수 있다. 하지만 물건의 개수가 최대 5,000개 임으로 수행시간이 최악의 경우 5000^3이다.

하지만, 물건 arr[i]와 arr[j]를 선택한 후에 C - (arr[i] + a[j])의 무게를 만족하는 물건을 찾는다면 2중 for문으로 해결할 수 있다.

• 입력된 물건의 무게 w를 chk[w]에 체크한다.
•  arr[i]와 arr[j]를 선택한다. arr[i] + arr[j] == C 또는 chk[C - (arr[i] + arr[j])] == true를 만족하면 종료한다.

 

3. 주의할 점

• 입력받은 물건의 무게 중에 무게 C와 동일한 것이 있다면 결과를 바로 출력하면 된다. 

 

4. 소스코드

#include <iostream>

using namespace std;

int N, M;
int arr[5001];
bool chk[100000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);


	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		chk[arr[i]] = true;
	}

	bool isOk = chk[M];
	if (!isOk) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (arr[i] + arr[j] == M) {
					isOk = true;
					break;
				}
				else if (arr[i] + arr[j] < M) {
					int diff = M - (arr[i] + arr[j]);
					if (chk[diff] && diff != arr[i] && diff != arr[j]) {
						isOk = true;
						break;
					}
				}
			}
			if (isOk) break;
		}
	}
	cout << isOk << '\n';

	return 0;
}