Project Euler #105 (Special subset sums: testing)

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

이전에 problem 106에서 사용한 unclear함수를 사용한다. - 문제 106번 보기

그리고 arr은 일종의 3진법이라 생각하면 될 것이다.

아래는 코드이다.

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

#define N 12

bool check_rule2(int num[N], int n) {
	int i;
	int sumB = 0, sumC = 0;
	for (i = 0; i < n; i++) {
		if(i < n/2 + 1) sumB += num[i];
		else sumC += num[i];
	}

	return sumB > sumC;
}

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-2;

	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 swap(int &x, int &y) {
	int t = x;
	x = y;
	y = t;
}

void sort(int *arr, int n) {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			if (arr[i] > arr[j]) {
				swap(arr[i], arr[j]);
			}
		}
	}
}

void main() {
	int m[N];
	int i, n, t, sumB, sumC;
	int cnt1, cnt2;
	int numbers[12];
	char line[100];
	char *token;
	bool satisfy;
	int satisfySum = 0;

	FILE *input = fopen("p105_sets.txt", "rt");
	printf("input = %s\n", (input == NULL ? "NULL" : "OPENED"));
	while (fscanf(input, "%s\n", line) != EOF) {
		token = strtok(line, ",");
		n = 0;
		while (token) {
			numbers[n] = atoi(token);
			n++;
			token = strtok(NULL, ",");
		}

		sort(numbers, n);

		for (i = 0; i < n; i++)
			printf("%4d ", numbers[i]);
		printf("\n");
		
		if (!check_rule2(numbers, n)) {
			printf("!!! oh no, unexpected case\n");
			continue;
		}

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

		satisfy = true;
		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) {
				satisfy = true;
				break;
			}

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

			sumB = 0; sumC = 0;
			for (i = 0; i < n; i++) {
				if (m[i] == 1) sumB += numbers[i];
				if (m[i] == 2) sumC += numbers[i];
			}

			if (cnt1 >= 2 && cnt1 == cnt2 && unclear(m, cnt1)) {
				if (sumB == sumC) {
					for (i = 0; i < n; i++) {
						printf("%4d ", m[i]);
					}
					printf("\n");
					printf("sumB = %d, sumC =%d\n", sumB, sumC);
					satisfy = false;
					break;
				}
			}
			
			if (cnt1 > cnt2 && sumB <= sumC) {
				satisfy = false;
				break;
			}
			if (cnt1 < cnt2 && sumB >= sumC) {
				satisfy = false;
				break;
			}

		}
		if (satisfy) {
			for (i = 0; i < n; i++) {
				satisfySum += numbers[i];
			}
			printf(">> this case satisfies both rules!\n");
		}
	}

	printf("satisfySum = %d\n", satisfySum);
	system("pause");
}