[Hackerrank][C++] Non-Divisible Subset

문제 링크: https://www.hackerrank.com/challenges/non-divisible-subset/problem

 

이 문제는 조건을 만족하는 부분집합(subset)중 가장 큰 부분집합의 크기를 구하는겁니다.

부분집합의 조건은 아무 두 원소의 합이 k의 배수가 아니어야 합니다.

 

일단 부분집합의 조건을 보면 입력값을 압축할 수 있습니다.

합이 k의 배수인지만 확인하면 되니까 입력값%k 값을 사용해 히스토그램으로 만들어줍니다. k<=100이기 때문에 10만개짜리 배열에서 100칸짜리 히스토그램으로 줄일 수 있습니다.

여기서 모든 부분집합을 만드는 경우는 k=100인 경우 2^100개 경우의 수가 나오는데 이건 너무 큰 값이니 불가능합니다.

 

합이 k가 되는 원소의 쌍을 생각해보면 (0, 0), (1, k-1), (2, k-2), ... , 이런식으로 되는데요, 두 원소가 동시에 배열에 들어갈 수 없으니 지금까지 더 많이 나온 mod값을 가진 수를 배열에 추가하면 됩니다.

유의할 점은 0은 한번만 들어갈 수 있고 k가 짝수일 때 k/2 역시 한번만 들어갈 수 있습니다. 두 번 들어가면 합이 k의 배수가 되기 때문입니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

ll histogram[100];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; ++i) {
		int tmp;
		cin >> tmp;
		++histogram[tmp % k];
	}

	ll subsets = 0;

	if (histogram[0])
		++subsets;

	for (int i = 1; i * 2 <= k; ++i) {
		if (i * 2 == k) subsets += (histogram[i] > 0);
		else subsets += max(histogram[i], histogram[k - i]);
	}

	cout << subsets << '\n';

	return 0;
}