Project Euler #106 (Special subset sums: meta-testing)

문제는 https://projecteuler.net/problem=106

문제를 해석하면 

1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
2. If B contains more elements than C then S(B) > S(C).

에서 특정 set이 rule ii를 만족한다는 가정하에 해당 set이 special한지를 확인하려면 몇 번의 테스트가 필요한가? 이다.

그리고 의미심장한 숫자를 몇 개 던지는데...

우선 n = 4 일 때 가능한 subset pair의 개수는 "25개"이며 이 중 "1가지" 경우만 확인하면 된다.

또 n = 7 일 때 가능한 subset pair의 개수는 "966개"이며 이 중 "70가지" 경우만 확인하면 된다.

그러면 n = 12 일 때 가능한 subset pair "261625개" 중 몇 가지의 경우만 확인하면 될까?

라고 말하고 있다.

중요한건 n=5 일 때나 n=6일 때에 대해서는 말하고 있지 않다는 점이다.

---

우선 25, 966, 261625의 숫자가 어떻게 발생하는지 생각해보자.

n = 4 일 때, subset의 개수는 2^4=16개로 나온다. 그 이유는 각각의 원소에 flag를 달아 0, 1 중 하나를 선택하게 하고 0은 subset에 존재 안함, 1은 subset에 존재로 표시하게 되면 2^4가 되기 때문이다.

그렇다면 문제에서 발생하는 subset pair, 즉 subset B, C가 disjoint하며 empty하지 않도록 나누는 방법은

각 원소에 flag가 0, 1, 2중 하나를 선택하게 하여

0은 존재 안함, 1은 set B에 존재, 2는 set C에 존재 하게 하여 우선 3^4=81가지 경우를 만든다.

그리고 set B와 set C가 둘다 empty가 되는 1가지 경우 {0, 0, 0, 0}를 빼면 80가지

그리고 이제 위의 80가지 중 set B가 empty가 되는 2^4 - 1 (왜냐면 set B는 empty가 아니므로 1을 뺀다), set C가 empty가 되는 2^4 - 1를 빼서, 80 - (2^4 - 1) - (2^4 - 1) = 50가지를 만든다.

그리고 set B와 set C는 원래 임의로 잡은 두 set이므로 중복을 빼기위해 2로 나누어 준다. 그러면 50/2 = 25가 나온다.

다시말해 가능한 subset pair의 개수는

로 표현된다. - 그러면 n = 4일 때 25, n = 7일 때 966, n = 12일 때 261625가 나온다.

이제 n = 4 일 때 "1가지", n = 7 일 때 "70가지"란 숫자가 어디서 나왔는지 생각해보자.

그리고 이제부터 {a1, a2, a3, a4}가 있을 때 {0, 1, 2, 1}로 나타내면 set B = {a2, a4}, set C = {a3}로 표현한다.

즉 n = 4일 때 크기비교가 모호한(아래 코드의 unclear function이 하는 일) 경우는 - set B와 set C의 원소를 일일히 더해 비교해 봐야 하는 경우는

{1, 2, 2, 1} 이 경우 밖에 없다!

왜냐면 {1, 2, 1, 2}는 a1 < a2, a3 < a4이므로 a1 + a3 < a2 + a4가 자명하기 때문이다.

또한 이 문제에서 set이 이미 rule 2를 만족한다고 고려하므로 1과 2의 개수가 같을 때만, 즉 pair의 개수가 2, 4, 6, ...일 때만 이 함수를 돌려주면 된다. (다시말해 n = 5일 때 {1, 2, 1, 2, 1}은 고려대상이 아니다.)

그럼 n = 5일 때는 어떻게 될까?

이 때는 {1, 2, 2, 1, 0}, {1, 2, 2, 0, 1}, {1, 2, 0, 2, 1}, {1, 0, 2, 2, 1}, {0, 1, 2, 2, 1} 의 5가지가 발생한다.

그럼 n = 6일 때는?

먼저 1과 2의 개수가 각각 2인: {1, 2, 2, 1, 0, 0}, {1, 2, 2, 0, 1, 0}, {1, 2, 2, 0, 0, 1}, {1, 2, 0, 2, 1, 0}, {1, 2, 0, 2, 0, 1}, {1, 2, 0, 0, 2, 1}, {1, 0, 2, 2, 1, 0}, {1, 0, 2, 2, 0, 1}, {1, 0, 2, 0, 2, 1}, {1, 0, 0, 2, 2, 1}, {0, 1, 2, 2, 1, 0}, {0, 1, 2, 2, 0, 1}, {0, 1, 2, 0, 2, 1}, {0, 1, 0, 2, 2, 1}, {0, 0, 1, 2, 2, 1} ,이렇게 (-)1(-)2(-)2(-)1(-) 의 (-)자리에 0두개를 적절하게 끼워넣어 만든 15가지 경우와 (이는 (5*4)/(2*1) + 5 = 15로 구할 수 있다) 

개수가 각각 인: {1, 1, 2, 2, 2, 1}, {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}, {1, 2, 2, 2, 1, 1} 5가지, 총 20가지다.

그런데 n = 7일 때는 "70개"란다! 규칙성이 보이는가?

규칙성은 사실... 없다!

그냥 모호한 경우를 계산하는 것이 최선이다. 그걸 위해 프로그래밍이 존재하지 않는가!

(사실 (-)1(-)2(-)2(-)1(-)사이 (-)공간에 0을 끼워넣는 방법과 {1, 1, 2, 2, 2, 1}, {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}, {1, 2, 2, 2, 1, 1}에서 빈 공간에 끼워넣는 방법 + 그리고 n = 짝수가 될때 마다 발생하는 경우에 대해 다시 고려.. 등으로 문제를 풀 순 있지만 너무 복잡하다)

그래서 아래의 unclear function이 필요하게 되는 것이다.

일단 함수부터 먼저 보자.

bool unclear(int arr[N], int pairs) {
	int i, j;
	int point = 0;
	bool first = true;
	i = N - 1; j = N - 1;

	int iter = 0;
	while (i >= 0 && j >= 0) {
		if (arr[i] != 1) {
			i--;
			continue;
		}
		if (arr[j] != 2) {
			j--;
			continue;
		}

		if (i < j) {
			if (first) {
				return false;
			}
			point++;
		}
		first = false;
		i--;
		j--;
	}
	return point != 0 && point != pairs;
}

i는 값이 1인 index, j는 값이 2인 index를 의미하고 이 함수에선 point제도를 사용한다. 

즉 i보다 큰 j가 발생할 경우 (잠깐: index가 N-1부터 훑는단걸 유의하라. 즉 {1, 2, 1, 1, 2, 2}에서 arr[5]는 1이다! - 제일 처음 숫자)

엔 point 1씩 얻는다.

그렇게 해서 point가 pairs이거나 (모든 i보다 j가 큼) point가 0일 때 (모든 i가 j보다 큼) 는 clear하고, 나머지 경우에 unclear함을 리턴한다.

이렇게 하면 1, 2, 2, 1 이나 1, 2, 1, 2, 2, 1은 각각 1점, 2점씩을 얻어 pairs보다 못미치므로 unclear하게된다.

아래는 전체 코드다.

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <windows.h>

#define N 12

int count(int arr[N], int p) {
	int i, count = 0;
	for (i = 0; i < N; i++) {
		if (arr[i] == p) count++;
	}
	return count;
}

bool unclear(int arr[N], int pairs) {
	int i, j;
	int point = 0;
	bool first = true;
	i = N - 1; j = N - 1;

	int iter = 0;
	while (i >= 0 && j >= 0) {
		if (arr[i] != 1) {
			i--;
			continue;
		}
		if (arr[j] != 2) {
			j--;
			continue;
		}

		if (i < j) {
			if (first) {
				return false;
			}
			point++;
		}
		first = false;
		i--;
		j--;
	}
	return point != 0 && point != pairs;
}

void main() {
	int m[N];
	int i, n;
	int cnt1, cnt2;
	int testcount = 0;

	// initialize m
	for (i = 0; i < N; i++) m[i] = 0;

	while (true) {
		m[0] ++;
		for (i = 0; i < N - 1; i++) {
			if (m[i] > 2) {
				m[i] = 0;
				m[i + 1]++;
			}
		}
		if (m[N - 1] > 1) break; //just break at 1

		cnt1 = count(m, 1);
		cnt2 = count(m, 2);

		if (cnt1 >= 2 && cnt1 == cnt2 && unclear(m, cnt1)) {
			testcount++;
		}

	}

	printf("testcount = %d\n", testcount);

	system("pause");
}

이제 105번을 풀어보자! - 문제 105번 보기